Find The Multiple
Time Limit:1000MSMemory Limit:10000K
Total Submissions:21436Accepted:8775Special 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
26190
Sample Output
10100100100100100100111111111111111111
Source
题意：输入一个正整数n（1<=n<=200），然后要求找一个只包含0和1的十进制数字能整除n
#include<iostream>#include<algorithm>#include<stdio.h>#include<string.h>#include<stdlib.h>#include<queue>using namespace std;int n;int ans;int v[5000];struct node{int x;int y;} a[1000010];void DFS(int k){int pt = a[k].y;if(pt <= 0){printf("1");return ;}DFS(pt);printf("%d",a[pt].x);}void BFS(){ans = 1;memset(v,0,sizeof(v));queue<node>q;struct node t,f;t.x = 1;t.y = 0;a[0].x = 1;a[0].y = 0;q.push(t);while(!q.empty()){t = q.front();q.pop();for(int i=0; i<=1; i++){f.x = t.x * 10 + i; /// 同余模定理应用if(v[f.x] == 0){f.x = f.x % n;f.y = ans;q.push(f);v[f.x] = 1;a[ans].x = i;a[ans].y = t.y;if(f.x == 0){DFS(ans);printf("%d\n",i);return ;}ans++;}}}}int main(){while(scanf("%d",&n)!=EOF){if(n == 0){break;}BFS();}return 0;}
版权声明：本文为博主原创文章，如有特殊需要请与博主联系 QQ ： 793977586。
，我喜欢出发。凡是到达了的地方，
