M01426: Find The Multiple

bfs, http://cs101.openjudge.cn/practice/01426/

Given a positive integer n, write a program to find out a nonzero multiple m of n whose decimal representation contains only the digits 0 and 1. You may assume that n is not greater than 200 and there is a corresponding m containing no more than 100 decimal digits.

输入

The input file may contain multiple test cases. Each line contains a value of n (1 <= n <= 200). A line containing a zero terminates the input.

输出

For each value of n in the input print a line containing the corresponding value of m. The decimal representation of m must not contain more than 100 digits. If there are multiple solutions for a given value of n, any one of them is acceptable.

样例输入

2
6
19
0

样例输出

10
100100100100100100
111111111111111111

来源

Dhaka 2002

"""
这是一个经典的BFS（广度优先搜索）问题，我们可以使用队列来解决。我们首先将1放入队列，然后在每一步中，我们取出队列的首元素，
然后生成两个新的数字：一个是在当前数字后面添加0，另一个是在当前数字后面添加1。我们将这两个新的数字添加到队列的末尾。
我们继续这个过程，直到找到一个数字可以被n整除。这个数字就是我们要找的结果。
"""
from collections import deque

def find_multiple(n):
    # 创建一个队列，并将1添加到队列中
    queue = deque(['1'])

    while queue:
        # 取出队列的首元素
        num = queue.popleft()

        # 如果这个数字可以被n整除，那么我们找到了结果
        if int(num) % n == 0:
            return num

        # 在当前数字后面添加0和1，然后将这两个新的数字添加到队列的末尾
        queue.append(num + '0')
        queue.append(num + '1')

def main():
    while True:
        n = int(input())
        if n == 0:
            break
        print(find_multiple(n))

if __name__ == "__main__":
    main()

【陈子良 25物理学院】做完才发现这是数算题。

看了一下题解，题解里好像都是在已知数的后面加0或1，我这个是在前面加0或1。

一个仅由0和1组成的数可以视为若干个10的x次方之和，如1101=1000+100+1。我们可以用x的列表来记录这个数，如1101就用[0,2,3]表示。

dp[i]表示这样一个列表，这个列表对应的数对n取模的值为i。对于每个10**x，它对n有一个余数a=10**x%n，对于dp中已经存在的数dp[i]，可以在其列表后方加上[x]生成dp[(i+a)%n]，所以这其实就是一个硬币问题。我们从0开始逐渐增大x，直到出现dp[0]输出其结果。

while True:
    n=int(input())
    if n==0:
        break
    dp={}
    x=0
    while True:
        a=10**x%n
        l=[]
        for i in range(n):
            if i in dp and (i+a)%n not in dp:
                l.append(i)
        for i in l:
            dp[(i+a)%n]=dp[i]+[x]
        if a not in dp:
            dp[a]=[x]
        if 0 in dp:
            print(sum([10**x for x in dp[0]]))
            break
        x+=1