问题97 - Project Euler :我的代码出了什么问题？

Question

我正在尝试使用python来解决Euler项目中的问题97。

我们的目标是找到28433×2^7830457+1的最后10位数字，但我的解决方案似乎有问题，而且我找不到问题所在。

我想过我的循环中有一个off-by-one错误，但添加或删除一个错误仍然会给出错误的答案，而且不管怎样，这个错误在逻辑上似乎是正确的。

有人能帮帮我吗？

谢谢

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

为了清楚起见，我将指出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

我不能从你的编辑中看出你是否已经明白了这一点，所以我想我应该提一下。

Answer 2

你的问题在这里

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

第一次发生这种情况时，基础是2 ^ 2，然后是2 ^ 4，然后是2 ^ 8 ... &c。

你需要重新考虑你的算法来计算2的幂。

Answer 3

这段代码：

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

不计算2^7830457。在每个循环基数都是2的幂之后，所以在第一次运行之后，你会得到base=4，然后是base=8，依此类推。