题意分析:1.求整数n(1 <= n < 10100)的后k位的循环节
         2.数据规模:1 <= n < 10100,k <= 100

算法分析:
直接枚举:用高精度乘法计算n的a次方,直到后k位出现循环,这样做有2个缺点:(1)时间复杂度过大,a的大小无法判断,可能会很超过MAXLONGINT,所以会超时 (2)无法判断不出现循环的情况
2.(1)可以发现,如果后k位循环,那么循环节一定是后k-1位循环的循环节的倍数
  证明如下:设后k位循环节为a1,后k-1位循环的循环节是a2,且a1=p*a2+b(p,b是常数)
           那么n^1的后k-1位=n^a2的后k-1位
               n^1的后k位=n^a1的后k位->n^1的后k-1位=n^a1的后k-1位
               所以n^a2的后k-1位等于n^a1的后k-1位...................................[1]
               因为b不是循环节,所以n^(p*a2)的后k-1位不等于n^(p*a2+b)的后k-1位
               n^(p*a2)的后k-1位等于n^a2的后k-1位
               所以n^a2的后k-1位不等于n^a1的后k-1位,这与[1]矛盾,
    所以我们可以求出后k-1位的循环节,再将后k-1位的循环节作为乘数求后k位的循环节(若n^a后k-1位与n的后k-1位相等,那么n^(a-1)为求后k位时的乘数),这样可以保证所枚举到的数一定是后k-1为循环节的倍数,而且可以大大减少枚举的数量
    可以通过记录后k位循环节长度是后k-1的循环节的多少倍来求循环节,这样,枚举的数就不需要用高精度,最后结果相乘时用高精度
  (2)整数的每一位有10种可能,如果某个长度枚举10次仍然没有循环的话,根据抽屉原理,因为这10个数中有1个没取到(就是该循环的一位)那么就一定出现了重复,也就是产生循环,但这个循环是以这9个数字中某个数开始的而不包括应该循环的那一位,那么意味着该循环的一位永远不会循环.那么这个时候就可以判断,这个数不会出现循环

这样做,上面直接枚举的2个问题都可以有效解决,

优化:
因为高精度计算中,计算后k位只需要保存后k位乘积的结果,而k范围较小,在计算是若判断大于k位则跳出,这样,节约了一定时间,同时也可以节约空间(因为结果只需存k位).
如果10次中已经出现循环的数,则可以退出


框架:
      for(int k=0;k<n;k++)//枚举循环的位数k
      for(int j=0;j<10;j++)//每一位最多有10种可能
      {
            a*=sqr;//做乘法,sqr是增加的倍数
            a1*=sqr;//a1记录下一次的增加的倍数
            If(a[k]=std[k])//若第k位产生循环
            {
                  sign=1;//标记产生循环
                  sol[total++]=j+1;//记录k位循环节长度是后k-1的循环节的多少倍
                  sqr=a;//改变乘数
                  break;
            }

      }


具体可以看
http://www.oibh.org/bbs/archiver/tid-16445.html,有程序
我就是直接copy的那个程序

• 牛人…… (0) HybridTheory 2007-10-04 00:27:22