问题97 - Project Euler：我的代码哪里错了？

Question

我正在用Python解决Project Euler的第97个问题。

这个问题的目标是找到28433×2^7830457+1的最后10位数字，但我写的代码好像不对，我也找不到问题出在哪里。

我想过可能是我的循环有个越界错误，但加一或减一后结果还是不对，而且从逻辑上看这个循环应该是没问题的。

有人能帮我吗？

谢谢

def PE97():
   mod = 10**10
   base = 2

    for i in range(7830456):
        base = (base * base)%mod

    print((28433*base+1)%mod)

PE97()

补充：算了，我发现我在写pow()函数时似乎很糟糕。

Answer 1

这段代码：

for i in range(7830456):
        base = (base * base)%mod

并没有计算出 2^7830457。在每次循环中，基数都会乘以2，所以第一次运行后，基数变成了4，接着是8，依此类推。

Answer 2

你的问题出在这里

base = 2
for i in range(7830456):
    base = (base * base)%mod

第一次发生的时候，基数是 2 ^ 2，接下来是 2 ^ 4，然后是 2 ^ 8，依此类推。

你需要重新考虑一下你计算二的幂的算法。

Answer 3

为了让大家更明白，我想说一下，Python自带的pow函数可以进行模幂运算，而且速度很快。

>>> pow(2, 5, 30)
2
>>> pow(2, 7830456, 6542)
5778
>>> timeit.timeit(stmt='pow(2, 5, 30)', number=100000)
0.031174182891845703
>>> timeit.timeit(stmt='pow(2, 7830456, 6542)', number=100000)
0.11496400833129883

我从你的修改中看不出来你是否刚刚明白这一点，所以我就提一下。