首页 > 代码库 > 编程之美---找符合条件的整数
编程之美---找符合条件的整数
题目：任意给定一个正整数N，求一个最小的正整数M(M>1)，使得N*M的十进制表示形式里只含有1和0.
解法：原问题转化为求一个最小的正整数X，使得X的十进制表示形式里只含有1和0，并且X被N整除。于是乎就成了遍历二进制整数一样遍历X的各个取值，但是如果X的最终结果又K位，则要循环搜索2K 次。因此，可以建立一个长度为N的“余数信息数组”，这个数组的第i位保留已经出现的最小的模N为i的X。用BigInt[i]可能很大，只须记下1的位置即可。
1 for(i=0;i<N;i++) 2 BigInt[i].clear(); 3 BigInt[1].push_back(0); 4 5 int NoUpdate = 0; 6 //i 表示当前最高位是 10^i 次方 j表示 10^i % N的值 100 % N = ((10 % N) * 10) % N 注意 j避免表示大数的方法 7 for(i=1,j=10%N; ; i++,j=(j*10)%N) 8 { 9 bool flag = false;10 if(BigInt[j].size()==0)11 {12 flag=true;13 //BigInt[j]=10^i,(10^i %N =j)14 BigInt[j].clear();15 BigInt[j].push_back(i);16 }17 for(k=1;k<N;k++)18 {19 if((BigInt[k].size()>0)&&(i>BigInt[k][BigInt[k].size()-1])&&(BigInt[(k+j)%N].size()==0))20 {21 //(i>BigInt[k][BigInt[k].size()-1])说明当前的余数不是因为在i循环时由早些的k循环处理中产生的22 //BigInt[(k+j)%N]=10^i+BigInt[k]23 flag=true;24 BigInt[(k+j)%N] = BigInt[k];25 BigInt[(k+j)%N].push_back(i);26 }27 }28 if(flag==false) NoUpdate++;29 else NoUpdate=0;30 //如果经过一个循环节都没能对BigInt进行更新，就是无解，跳出。或者BigInt[0]!=NULL,已经找到解，也跳出31 if(NoUpdate==N||BigInt[0].size()>0)32 break;33 }34 if(BigInt[0].size()==0)35 {36 // M not exist;37 }38 else 39 {40 //Find N*M=BigInt[0]41 }
网上一个证明这M一定存在的思想：
解决这个问题首先考虑对于任意的N，是否这样的M一定存在。可以证明，M是一定存在的，而且不唯一。
简单证明：因为
这是一个无穷数列，但是数列中的每一项取值范围都在[0, N-1]之间。所以这个无穷数列中间必定存在循环节。即假设有s,t均是正整数，且s<t，有 。于是循环节长度为t-s。于是10^s = 10^t。因此有：
，所以
编程之美---找符合条件的整数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。