题解：P1050 [NOIP 2005 普及组] 循环

· · 题解

begin

P1050 [NOIP 2005 普及组] 循环

前言

注意数据范围：1\le n \le 10^{100} ，1\le k \le 100。

所以这题要写高精……吗？

那么既然我都这么问了，那么答案肯定是否定的，所以本片题解是一篇 Python 题解，但是思路应该是差不多的。

题目大意

给定 n ，k，求 n 的正整数次幂后 k 位的循环节长度。若无解输出 -1。

思路

有一种思路大家肯定都能想到，就是一直翻倍直到找到循环节，如果超出了一定限度就判定为无解。

咱们姑且不说最大限度定为多少，就这个思路写出来包 T 飞的。

我们考虑一下如何进行优化。

我们思考一下如何在确定后 k 位循环节的情况下快速找出后 k+1 位的循环节。

我们发现，后 k+1 的循环节的位数必定是后 k 位的循环节的位数的倍数，因为题目中提到了这样一句话：

如果循环长度是 L，那么说明对于任意的正整数 a，n 的 a 次幂和 a+L 次幂的最后 k 位都相同。

我们既然想要后 k+1 位都相同，那么前提是后 k 位必须相同，那也就是必须保证未知循环节的位数是原循环节位数的倍数，因为只有后 k 位一样，后 k+1 位才有可能一样。

实践操作

我知道光看着文字叙述可能还是一头雾水地感觉很绕（事实上我写这篇题解的时候也是这么觉得的）。

不过没关系，我们来手搓一组数据就明白了。

（如果听懂了的话就可以略过这部分去看代码了。）

数据：

input:
123456(n) 4(k)

output:
125(ans)

explain:
123456%10^4=3456
(10^4->mod)

Part 1(6):
3456                       1
3456*3456=11943936->393{6} #
3456^1=3436->3456

Part 2(56):
3456                       1
3456*3456=11943936->3936   2
3936*3456=13602816->2816   3
2816*3456=9732096->2096    4
2096*3456=7243776->3776    5
3776*3456=13049856->98{56} #
3456^5=493024690386763776->3776 (a)

Part 3(456):               (3->i)
3456 (m)                   1
3456*3776=13049856->9856   2
9856*3776=37216256->6256   3 (j)
6256*3776=23622656->2656   4
2656*3776=10029056->2656   5
9056*3776=34195456->5{456} #
3776^5=767644120830181376->1376 (q)

Part END(3456):
3456                       1
3456*1376=4755456->5456    2
5456*1376=7507456->7456    3
7456*1376=10259456->9456   4
9456*1376=13011456->1456   5
1456*1376=2003456->{3456}  #

ans=1*5*5*5=125

Code

# 这里面各种变量名都在上面的数据解释中有所体现。
n,k=map(int,input().split())
ans=1
mod=10**k
n%=mod
m=0
a=n
for i in range(1,k+1):
    flag=True # 判断是否有解
    m=n
    q=1
    for j in range(1,11): # 这里只用循环十次是因为最多只有 0~9 一共 10 个整数，超出就意味着无解。
        m*=a
        m%=mod
        q*=a
        q%=mod
        if m%10**i==n%10**i:
            ans*=j
            a=q
            flag=False
            break
    if flag:
        print(-1)
        exit(0)
print(ans)

时间复杂度 O(10k)。

end