使求和幂级数更高效

Question

我在 hackerrank 中编码并遇到了这个问题： https://www.hackerrank.com/challenges/power-calculation

我的代码适用于小文件和大数字。至于大文件，它会超时。有人可以让它更有效率吗？

我的代码：

 z = []
def modexp(a, n, m):
    bits = []
    while n:
        bits.append(n%2)
        n /= 2
    solution = 1
    bits.reverse()
    for x in bits:
        solution = (solution*solution)%m
        if x:
            solution = (solution*a)%m
    return solution


for _ in xrange(int(input())): 
    while True: 
            try:
                    x = raw_input()
                    sum =0
                    z = x.split(' ')
                    power = int(z[1])
                    limit = int(z[0])
                    for i in range(0,limit+1): 
                        sum = sum%100 + modexp(i%100,power, pow(10,2))
                    if sum < 10: 
                        print '%02d' % sum 
                    if sum > 10: 
                        print sum%100 
            except: 
                break

示例数据 - 输入：

10
487348 808701
204397 738749
814036 784709
713222 692670
890568 452450
686541 933150
935447 202322
559883 847002
468195 111274
833627 238704

示例输出：

Answer 1

通过观察其值 mod 100 的周期为 100，可以轻松减少幂评估的次数。因此通过计算 M=K/100; L=K%100; 分解 K = M*100+L。

然后

对于k=0到L次幂modexp(k%100,N,100)出现M+1次，
对于 k=L+1 到 99 它在总和中出现 M 次。

这样每次幂和可以减少到99次幂计算

通过观察相同数字的递增幂在最后两位数字中是周期性的，可以进一步减少计算幂的工作量。一般序列

1, a % m, a**2 % m, a**3 % m, a**4 % m, ...

在素因子的最高重数给出的某个点之后变得周期性。一个周期长度由欧拉 totient 函数中 m 的值给出。

100=2²·5²的总值是phi(100)=(2-1)·2·(5-1)·5=40。在句点设置之前的偏移量最多为 2，因此对于所有整数 a

a**2 % 100 == a**42 % 100 = a**82 % 100 = ...
a**3 % 100 == a**43 % 100 = a**83 % 100 = ...

等等。

这意味着对于 N>41 可以将指数减少到 N=2+(N-2) % 40。（事实上，在该减少中可以将 40 替换为 20。）

作为最后的评论，不会对运行次产生太大影响，只会影响代码的复杂性：

有一个更短的实现方式modexp，这个算法也是识别循环不变量的标准练习：

def modexp(a, n, m):
    solution = 1
    apower = a
    while n:
        if (n%2): solution = (solution*apower) % m
        n /= 2
        apower = (apower*apower) % m
    return solution

使求和幂级数更高效

Make summing power series more efficient

python-2.7

math

modulus