Find The Multiple
| Time Limit: 1000MS | Memory Limit: 10000K | |||
| Total Submissions: 28550 | Accepted: 11828 | 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
Source
原题大意：找出任意一个只由0与1组成的数，使得其为n的倍数。
解题思路：问题在于对问题的优化。100位数字太长了（当然，实际到不了100位，最高19位左右），若是找余数的状态，又很难数清有多少种。于是可以先来一个裸的搜索先判最长位数，然后用深搜或广搜解题。
#include<stdio.h>
int n,ans[400];
bool found;
void dfs(int mod,int dep)
{
if(found || dep>19) return;
if(mod==0)
{
for(int i=0;i<=dep;++i) printf("%d",ans[i]);
printf("
");
found=true;
return;
}
ans[dep+1]=1;
dfs((mod*10+1)%n,dep+1); //mod的运算规律，可以这样想：假设X为当前位以前所有的数，那么当前数为X*10+i(i=0/1),对其取n的余数，(X%n*10%n+i%n)%n,递推即可。
ans[dep+1]=0;
dfs((mod*10)%n,dep+1);
}
int main()
{
int i;
while(~scanf("%d",&n))
{
if(n==0) break;
found=false;
ans[0]=1;
dfs(1%n,0);
}
return 0;
}