E - Find The Multiple POJ - 1426
E - Find The Multiple POJ - 1426
Find The Multiple
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.
测试样例
2 6 19 0
样例输出
10 100100100100100100 111111111111111111
题意理解:
- 输入多组数据,每组数据只有一行,每行包括一个数n。
- 对于每组数据输出一个只包含0和1的十进制数m。
- m是n的倍数。
- 如果有多组符合条件的m输出其中一组即可。
解题思路:
这道题表面上既不是求最呦也不是求全部解,只要求一组姐就可以,我得第一反应是用bfs,第一个数一定是1,每次只要存一下后面加0加1两种情况就可以了,但是很明显内存不够
爆内存了,然后改用dfs,写到一半觉得时间应该不够,看了一下网上代码,发现我误入了大整数的坑,我是把每个数各个位都存一下然后再传到求大整数取余的函数里for循环,大佬的代码是每加一位就直接在递归传参时把余数算出来,节省很多时间和空间。
代码如下:
代码:
#include<iostream>
#include<cstring>
using namespace std;
char s[105];
bool flag;
void dfs(int mod,int d,int n)
{
if(d>100) return ;
if(mod==0)
{
flag=true;
s[d]=0;
return ;
}
if(!flag)
{
s[d]='0';
dfs((mod*10)%n,d+1,n);
}
if(!flag)
{
s[d]='1';
dfs((mod*10+1)%n,d+1,n);
}
}
int main()
{
while(1)
{
int m;
cin>>m;
if(m==0)
break;
memset(s,0,sizeof(0));
s[0]='1';
flag=false;
dfs(1,1,m);
cout<<s<<endl;
}
return 0;
}