首页 > 代码库 > 编程之美——符合条件的整数

编程之美——符合条件的整数

2024-07-17 19:30:49   217人阅读

问题：给定整数N，求最小整数M，使得N*M的十进制表示中只含有1和0；

        当M很大时，机器可能不能表示M，对问题转化：求以最小整数X，使得X的十进制表示中只含1和0，并且被N整除；

        此问题必定有解；可参考：http://blog.csdn.net/spaceyqy/article/details/38337387

代码实现（具体思路参考编程之美或：http://www.cnblogs.com/jfcspring/p/3776388.html）：

 1 #include<iostream> 2 #include<vector> 3 #include<string> 4 using namespace std; 5  6 const int N=6; 7 vector<vector<int> >bigInt; 8  9 void findNum();10 void printNum(const vector<int> &t);11 12 int main()13 {14     findNum();15     return 0;16 }17 18 void findNum()19 {20     for(int i=0;i<N;++i)21     {22         vector<int>tt;23         bigInt.push_back(tt);24     }25 26     bigInt[1].push_back(0);27     28     //i:记录每一个数组中1的位置29     //j:余数，为数组下标30     for(int i=1,j=10%N;;++i,j=(10*j)%N)31     {32         if(bigInt[j].size()==0)33         {34             bigInt[j].push_back(i);35         }36 37         for(int k=0;k<N;++k)38         {39 40             int t=(k+j)%N;41             if((bigInt[k].size()>0)&&(i>bigInt[k][bigInt[k].size()-1])&&(bigInt[t].size()==0))42             {43                 //(1,3,4)=(1,3)+(4)44                 bigInt[t]=bigInt[k];45                 bigInt[t].push_back(i);46             }47         }48 49         if(bigInt[0].size()>0)50         {51             printNum(bigInt[0]);52             break;53         }54     }55 }56 57 //(0,3,4) represent 1100158 void printNum(const vector<int> &t)59 {60     int maxIndex=t.back();61     string num="";62 63     for(int i=0;i<maxIndex+1;++i)64         num+=‘0‘;65 66     for(int i=0;i<t.size();++i)67         num[maxIndex-t[i]]=‘1‘;68 69     for(int i=0;i<num.size();++i)70         cout<<num[i];71 }
View Code

 


联系
我们