1 //Memory Time 2 //2236K  32MS  3  4 #include<iostream> 5 using namespace std; 6  7 int mod[524286];  //保存每次mod n的余数 8                   //由于198的余数序列是最长的 9                   //经过反复二分验证，436905是能存储198余数序列的最少空间10                   //但POJ肯定又越界测试了...524286是AC的最低下限，不然铁定RE11 12 int main(int i)13 {14     int n;15     while(cin>>n)16     {17         if(!n)18             break;19 20         mod[1]=1%n;  //初始化，n倍数的最高位必是121 22         for(i=2;mod[i-1]!=0;i++)  //利用同余模定理，从前一步的余数mod[i/2]得到下一步的余数mod[i]23             mod[i]=(mod[i/2]*10+i%2)%n;24                      //mod[i/2]*10+i%2模拟了BFS的双入口搜索25                      //当i为偶数时，+0，即取当前位数字为0  。为奇数时，则+1,即取当前位数字为126 27         i--;28         int pm=0;29         while(i)30         {31             mod[pm++]=i%2;   //把*10操作转化为%2操作，逆向求倍数的每一位数字32             i/=2;33         }34         while(pm)35             cout<<mod[--pm];  //倒序输出36         cout<<endl;37     }38     return 0;39 }