1426:Find The Multiple

PKU

keyword

BFS　Python

概要

N<200が与えられたとき、10進表記で0と1しか出てこないような倍数を求める問題。
mod Nだけ考えて枝刈りしつつ探索すればよい。答えが小さいのと多倍長の可能性があるのでPythonで書いてソースに埋め込む。結果的に全てlong longで何とかなっていた。

import sys

def solve(n):
    visited = [False for i in range(n)]
    cur = [1]
    while(True):
        nxt = []
        for e in cur:
            n1, n2 = e*10, e*10+1
            if(n1%n == 0): return n1
            if(n2%n == 0): return n2
            if(not visited[n1%n]):
                visited[n1%n] = True
                nxt.append(n1)
            if(not visited[n2%n]):
                visited[n2%n] = True
                nxt.append(n2)
        cur = nxt

for n in range(2,201):
    sys.stdout.write('%dll, ' % (solve(n)))