题目：任意给定一个正整数N，求一个最小的正整数M(M>1)，使得N*M的十进制表示形式里只含有1和0。解法一：暴力求解。从1开始查找M，然后判断M*N=X这个数字是否只含有0,1.
解法二：由于没有直接的数学方法能帮我们直接得到M的值，所以我们只能进行搜索。由于相对M，乘积N*M具有明显的特征，需要搜索的空间要小很多，所以我们对乘积N*M进行搜索。如果N*M的结果有K位，则要循环2^K次，我们发现K的结果能轻易超过40，所以这个运行时间还是相当长。同余运算具有等价关系，mod N = i（0<=i<N）构成了N个等价类，将正整数集进行划分。对于每个等价类，我们只需要判断其中最小的元素加上10^K是否能被N整除，这样搜索空间就从2^K次减少到(K-1)*N步，而N的值一般要远远小于M的值，但要O(N)的空间复杂度。
由于无论M还是N*M的位数都相当大，所以我们用大整数表示M和N*M。由于要N个大整数，所以N不能为大整数，即其值最好取一百万以内。
代码实现入下：
#include<iostream>#include<cmath>#include<vector>using namespace std;bool FindNumber(int N,vector<int> *BigInt);int main(){int N,i;cout<<"Input a positive integer: ";cin>>N;vector<int> *BigInt=new vector<int>[N];//用来存放余数为0 ~ N最小数字，数字表示，如整数1001，则存为1001=10^0+10^3=(0,3)，适合大数的表示for(i=0;i<N;i++)BigInt[i].clear();bool found=FindNumber(N,BigInt);if(found){int len=BigInt[0][BigInt[0].size()-1]+1;char *product=new char[len+1];int product2=0;for(i=0;i<len;i++)product[i]='0';product[len]='\0';vector<int>::iterator iter;for(iter=BigInt[0].begin();iter!=BigInt[0].end();iter++){product2=product2+pow(10,*iter);product[*iter]='1';}int j=len-1;i=0;while(i<j){char tmp=product[j];product[j]=product[i];product[i]=tmp;i++;j--;}int M=product2/N;//product和product2都对应着乘积结果，但是product2对应着整型，乘积过大时，product2可能不会得到正确的结果；//product对应着乘积的字符串，可以表示大数的乘积结果，M为product2/N，即为要求的数，当product2溢出时，不是正确的结果,//那种情况下，需要用product/N，其中product为乘积的字符串表示，这里没有求解，读者可以自行解决。cout<<N<<" * "<<M<<" = "<<product<<" , "<<product2<<endl;delete []product;}elsecout<<"Can not find M!"<<endl;delete []BigInt;return 0;}bool FindNumber(int N,vector<int> *BigInt){int i,j,k;BigInt[1].push_back(0);int NoUpdate=0;for(i=1,j=10%N; ; i++,j=(j*10)%N){bool flag=false;if(BigInt[j].size()==0){flag=true;// BigInt[j]=10^i,(10^i)%N=jBigInt[j].clear();BigInt[j].push_back(i);}for(k=1;k<N;k++){//有新的余数出现if((BigInt[k].size()>0)&&(i>BigInt[k][BigInt[k].size()-1])&&(BigInt[(k+j)%N].size()==0)){//BigInt[(k+j)%N]=10^i+BigInt[k]flag=true;BigInt[(k+j)%N]=BigInt[k];BigInt[(k+j)%N].push_back(i);}}if(flag==false)NoUpdate++;elseNoUpdate=0;//如果经过一个循环节都没能对BigInt进行更新，就是无解，跳出,//若有N次没更新过余数信息，则存在c>=0,10^(c+1)modN,...,10^(c+N)modN中必有两个是相等的，//那么继续进行下去也不会再更新了//或者BigInt[0]!=NULL,已经找到解，也跳出.if(NoUpdate==N||BigInt[0].size()>0)//若有N次没更新过余数信息，则存在c>=0,10^(c+1)modN,...,10^(c+N)modN中必有两个是相等的，那么继续进行下去也不会再更新了break;}if(BigInt[0].size()==0)return false;elsereturn true;}
我们可以证明对于任意的N，一定存在M，使得N*M的乘积的十进制表示只有0和1。证明过程见:/jcwkyl/article/details/3859155
