编程之美：找到符合条件的整数

编程之美：找到符合条件的整数2015-02-11一、问题描述

任意给定一个正整数N,求一个最小正整数M（M>1），使得N*M的十进制形式只含1和0。

比如 N=99,M=1 122 334 455 667 789 ,N*M=111 111 111 111 111 111;

M就是当N=99时，符合条件的数

二、解题思路

考虑将问题转化为：找只含有0和1的能被N整除的最小正整数。可以看出这是和原问题等价的。

那么需要将0和1组成的所有数从小到大遍历吗？这样的话，如果寻找的数是k位，则需要搜索2k-1个数才能得到结果。

这里采用的方式是在计算中保留%N的余数信息，避免不必要的计算。更形式化的论述：

假如已遍历了所有K位（X）十进制数，而且也搜索了T=10k（10的k+1位数的最小数），现在要考察所有k+1为数（Y）的情况。则

Y=X+T（即所有K进制的数+10K），如果我们将X按%N将空间分解，即将X分解成余数为（0~N-1）的等价类，则在搜索Y是只需要取X中的代表元素进行模运算，这样就将搜索时间从2K降到N。在具体实现时每个等价类中都保存最小的元素。

三、代码实现

#include<iostream>#include<vector>#include<string>#define N 100213using namespace std;vector<vector<int> >BigIntVec;void printNum（const vector<int>& tv）{//cout<<"print"<<endl;int maxIndex=tv.back（）;string numStr=""; for（int i=0;i<maxIndex+1;i++）{numStr+="0";}for（int i=0;i<tv.size（）;i++）{numStr[maxIndex-tv[i]]="1";}cout<<"找到的最小符合条件的数为："<<endl;for（int i=numStr.size（）-1;i>=0;i--）{cout<<numStr[i];}cout<<endl;}void findNum（）{for（int i=0;i<N;i++）{vector<int>tt;BigIntVec.push_back（tt）;}BigIntVec[1].push_back（0）;int noUpdate=0;for（int i=1,j=10%N;;i++,j=（j*10）%N）{ bool flag=false;if（BigIntVec[j].size（）==0）{BigIntVec[j].push_back（i）;flag=true;} for（int k=0;k<N;k++）{ if（BigIntVec[k].size（）>0&&i>BigIntVec[k].back（））{ int t=（k+j）%N; if（BigIntVec[t].size（）==0）{ for（int tt=0;tt<BigIntVec[k].size（）;tt++）{BigIntVec[t].push_back（BigIntVec[k][tt]）;}BigIntVec[t].push_back（i）;flag=true;}} } if（flag==false）{noUpdate++;}else{noUpdate=0;}if（BigIntVec[0].size（）>0||noUpdate==N）{ break;}}if（BigIntVec[0].size（）>0）{printNum（BigIntVec[0]）;}else{cout<<"没有找到符合条件的数"<<endl;}} int main（）{findNum（）;system（"pause"）;return 0;}

注：由于该问题涉及到的整数可能非常大，不能用内置类型int或long表示，因此程序中借助vector实现模拟整数。因为寻找的数只有1,0两种数字，为了节省空间，每个整数用vector<int>表示，vector每一元素保存1出现的位置。例如数字100101，的vector<int>表示为{0,2,5}，即出现1的位置分别为第0,2,5位。

四、程序输出结果（输入N为：100213）：

From：cnblogs jfcspring