[深度优先搜索] POJ 1426 Find The Multiple

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("\n");
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;
}

  

              
上一篇:JAVA自学笔记14


下一篇:【Android】14.0 第14章 内部存储与外部SD卡存储—本章示例主界面