2016"百度之星" - 初赛（Astar Round2A）1001 All X（HDU5690）—

　　一个由m个数字x组成的新数字，问其能否mod k等于c。

　　先提供第一种思路，找循环节。因为每次多一位数都是进行(t*10+x)mod k（这里是同余模的体现），因为x，k都确定，只要t再一样得到的答案一定一样。所以在一步一步中进行时一旦出现了一个之前出现过的数字，那么很显然后面就要开始进行循环了。找出这个循环节，然后把m放到这个循环节里头就行（这里的说法有问题，见下文的第二点）。

　　但是这里有两个要注意的地方，第一是只有当前出现的数一样才能保证下一个出现的数一样，而并不代表着，当前的数一样，得到它的数就一样，因此，第一个数并不一定参与循环。不妨举个最简单的例子，这一系列的数字是，3，4，5，6，4，5，6，4，5，6。。。第一个3并不参与循环。其实也好理解，一个分数，其分母和分子一样，所以也相当于一直进行同样的操作，最后一定会处于循环状态（不循环的话视作一直0循环），但是很显然的第一位小数不一定是参与循环的部分。

　　第二点是，基于上一点，m如果较小的话不一定处于循环节内，那么就没办法把它放到循环节里头，那么直接从1算到m即可。

　　下面给出的学长的代码，很巧妙的解决了所有的问题：

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 using namespace std;

 typedef long long LL;

 const int N =  + ;

 LL pos[N];

 LL x, m, k, c;

 int main(){

     int T;

     int cas = ;

     scanf("%d", &T);

     while(T --){

         memset(pos, -, sizeof(pos));

         scanf("%I64d%I64d%I64d%I64d", &x, &m, &k, &c);

         printf("Case #%d:\n", cas ++);

         int tmp = ;

         LL d;

         for(LL i = ; i <= m; i ++){

             tmp = tmp *  + x;

             tmp %= k;

             if(pos[tmp] == -){

                 pos[tmp] = i;

             }else{

                 d = i - pos[tmp];

                 i += (m - i) / d * d;

                 if(i > m) i -= d;

                 for(LL j = i+; j <= m; j ++){

                     tmp = tmp *  + x;

                     tmp %= k;

                 }

                 break;

             }

         }

         if(tmp == c) puts("Yes");

         else puts("No");

     }

 }

　　第二种方法是快速幂，很巧妙，直接搬运别人的博客了：http://www.cnblogs.com/inmoonlight/p/5515538.html 直接没几行代码就没了，也是厉害。。

巴特西

2016"百度之星" - 初赛（Astar Round2A）1001 All X（HDU5690）——找循环节|快速幂

最新文章

热门文章