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.
大意就是说求一个只有0，1的数，是n的倍数。
其实是一个水题，第一遍做的时候直接枚举1，10，11，100，101，110，111...一直这样下去，然后就过了。。。。后来看了一下题解，说可以用BFS+同余来做，然后就试了一下，时间减去了不少。
而且这个题目对于n是偶数或者n是5的倍数可以直接求出n／2或n／5的来然后加个0就好了。。。
这是第一遍的代码：
#include<iostream>
#include<cstring> using namespace std; long long ans[]; bool panduan(int a,int b)
{
long long num=;
long long base=; while(b)
{
if(b%)
num+=base;
base*=;
b/=;
} if(num%a==)
{
ans[a]=num;
return ;
} return ;
} int main()
{
int cou=;
for(int i=;i<=;i+=)
if(i%)
{
for(int j=;j<(<<);++j)
if(panduan(i,j))
{
break;
}
} int k,rem; ios::sync_with_stdio(false); for(cin>>k;k;cin>>k)
{
rem=;
while(k%==)
{
k/=;
++rem;
}
while(k%==)
{
k/=;
++rem;
}
cout<<ans[k];
for(int i=;i<rem;++i)
cout<<;
cout<<endl;
} return ;
}
这是第二遍的：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<utility> using namespace std; int que[],las,fir; void showans(int x)
{
int ans[];
int cou=; while(x)
{
if(x&)
ans[cou++]=;
else
ans[cou++]=; x=x>>;
} for(int i=cou-;i>=;--i)
cout<<ans[i]; cout<<endl;
} inline void getans(int n)
{
las=fir=; int cou=;
int temp; que[las++]=; while(las-fir)
{
++cou;
temp=que[fir++]; if(!temp)
{
showans(cou);
return;
} que[las++]=(temp*)%n;
que[las++]=(temp*+)%n;
}
} int main()
{
ios::sync_with_stdio(false); int n; for(cin>>n;n;cin>>n)
{
getans(n);
} return ;
}