Find The Multiple
| Time Limit: 1000MS | Memory Limit: 10000K | |||
| Total Submissions: 33882 | Accepted: 14173 | Special Judge | ||
Description
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.
Input
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.
Output
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.
Sample Input
2 6 19 0
Sample Output
10 100100100100100100 111111111111111111
题意：给你一个int范围内的正整数n，输出能够整除这个正整数n且由01组成的任意一个数x。
思路：同余定理的应用，所求x是能整除n的数，但是现在x我们未知，只能一步一步从高位到低位递推出x。
由于x只能由01序列组成，所以我们每次从x的最高位到低位进行查找的过程中有两个选择，取0或者取1，最高位只能为1。
如果我们用bfs模拟除法运算这个过程，用一个数组mod记录每次的余数且每次将mod[i]%10+str[i]-'0'对n取余的余数入队，下一次进行运算时，就能通过mod[i-1]得到
mod[i],不过我自己用bfs超时到爆炸，不知道咋回事，就换成了一位大佬的方法，用数组模拟bfs。
借鉴博客
#include<stdio.h> #define N 600000 long long mod[N],num[N],n; int j,i; int main() { while(scanf("%lld",&n),n!=0) { i = j = 1; mod[i++] = 1%n;//初始化x的最高位数 while(mod[i-1]!= 0) {//mod[i/2]是上一步取余的结果 mod[i] = (mod[i/2]*10+i%2)%n;//模拟bfs双入口搜索 i++;//解释：i%2,i为偶数时,模拟+0，i为奇数时,模拟+1 } i--; while(i) { num[j++] = i%2; i/=2; } while(j > 1) {//逆序输出 printf("%d",num[--j]); } printf(" "); } return 0; }