kb-01-e<取余操作，宽搜，巧妙>；

题目描述：

n属于1到200，找到对应的一个数只含有0和1，并且是n的倍数；

分析：

本题有几个数会是大数；所以要考虑大数；

用到余数的性质；例如n=6，1%6=1；

1*10%6=4；（1*10+1）%6=5；

4*10%6=4；（4*10+1）%6=5；

5*10%6=2；（5*10+1）%6=3；

（重复4，5）

2*10%6=2；。。。。=3；

3*10%6=0；

这时候发现余数为0，说明这个数可以是6的倍数；倒退回去，数分别是1，10，11，100，101，110，111，。。。。1110；

可以发现余数是一样的，同余定理；

（a*b）%n = （a%n *b%n）%n

（a+b）%n = （a%n +b%n）%n

由同余模定理 (110*10+1)%6 = (（110*10）%6+1%6 )%6 = (（110%6 * 10%6）%6 +1 )%6；

用这个同余定理就可以解决大数问题了；然后就是记录路径，这里就是巧妙的地方；我还不太清除是怎么搞的，总之就是一共进行了k次操作，就相当于01全排列，首项是1，然后排到第一个符合的数的时候，这个数是第几个，它对应的二进制就是相应的串；这一题用bfs居然超时了；所以我打了个表，有一个不打表的做法；

代码如下：

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<cstring>

 #include<queue>

 using namespace std;

 queue<int> q;

 int n;

 char a[][]={"","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","","",""};

 /*

 int cou=0;

 void bfs()

 {

     while(!q.empty())

     {

         int t=q.front();

         q.pop();

             cou++;

         if(t%n==0)

             return;

         q.push(t*10%n);

         q.push((t*10+1)%n);

     }

 }

 int main()

 {

     freopen("out","w",stdout);

     for(int z=1;z<=200;z++)

     {

         n=z;

         while(!q.empty())

             q.pop();

         memset(a,0,sizeof(a));

         cou=0;

         a[0]=1;

        q.push(1);

        bfs();

        int i=0;

        while(cou)

        {

            a[i++]=cou%2;

            cou=cou/2;

        }

        printf("\"");

        for(int j=i-1;j>=0;j--)

        {

            printf("%d",a[j]);

        }

        printf("\",");

     }

     return 0;

 }*/

 int main()

 {

     while(cin>>n&&n)

     {

         printf("%s\n",a[n-]);

     }

     return ;

 }

 //Memory Time

 //2236K  32MS 

 #include<iostream>

 using namespace std;

 int mod[];  //保存每次mod n的余数

                   //由于198的余数序列是最长的

                   //经过反复二分验证，436905是能存储198余数序列的最少空间

                   //但POJ肯定又越界测试了...524286是AC的最低下限，不然铁定RE

 int main(int i)

 {

     int n;

     while(cin>>n)

     {

         if(!n)

             break;

         mod[]=%n;  //初始化，n倍数的最高位必是1

         for(i=;mod[i-]!=;i++)  //利用同余模定理，从前一步的余数mod[i/2]得到下一步的余数mod[i]

             mod[i]=(mod[i/]*+i%)%n;

                      //mod[i/2]*10+i%2模拟了BFS的双入口搜索

                      //当i为偶数时，+0，即取当前位数字为0  。为奇数时，则+1,即取当前位数字为1

         i--;

         int pm=;

         while(i)

         {

             mod[pm++]=i%;   //把*10操作转化为%2操作，逆向求倍数的每一位数字

             i/=;

         }

         while(pm)

             cout<<mod[--pm];  //倒序输出

         cout<<endl;

     }

     return ;

 }

巴特西

kb-01-e<取余操作，宽搜，巧妙>；

最新文章

热门文章