计算i^2453467 mod 2453468的总和为1 <= i <= 999999（^意味着功率）

Question

如何在更短的时间内有效地完成这类问题？我试图用Python来解决这个问题，但它花费了很多时间。我一直在想，也许^意味着xor不是权力，但根据他们这是权力。这是编码竞赛的一个问题。

Answer 1

在Python代码

answer = 0 
for i in range (1, 1000000): 
    answer += pow(i, 2453467, 2453468) 
print answer % 2453468 

速度似乎不够快

Answer 2

https://en.wikipedia.org/wiki/Modular_exponentiation

聚焦计算的存储器高效的方法。应该是相当简单的实施。

Answer 3

在一般的情况下，是的，你应该更好地利用模幂，这的确是相当简单，如@ F.Ju。然而，用一点数学，你可以用笔和纸完全计算总和。

关键要注意的是指数（2453467）非常接近模数（2453468），这就需要一个更简单的表示x^2453467 mod 2453468。事实上，如果2453468是素数，则根据Fermat's little theorem，x^2453467 mod 2453468总是1。

虽然这不是首要的，但它有一个非常简单的表示2*2*613367。所以我们可以记住Euler's theorem，发现phi(2453468)等于1226732，所以2453467=2*phi(2453468)+3。因此，对于与2453468相对较好的每个x，我们有x^1226732=1，并且，因为2453467是1226732*2+3，所以我们有x^2453467 mod 2453468=x^3 mod 2453468。

让我们再考虑一些不是2453468的质数。在超出范围（1至999999）中，有三种数字与2453468不相对。一个是613367，并且相对容易证明613367^(2k+1) mod 2453468=613367为每个k。

另一种是可被4整除的数字。对于数字x=4k，我们需要找到(4k)^2453467 mod (4*613367)。它相当于4*(4^2453466*k^2453467 mod 613367) mod (4*613367)，稍微有一点费马定理，这减少到(4k)^3 mod (4*613367)。

最后一种是可以被2整除的数字，但不是4，它们的处理方式与前一种相同。

其结果是，我们有

每x从1到999999，

x^2453467 mod 2453468 = x^3 mod 2453468 

因此，我们需要从计算

sum(x^3) mod 2453468 

为x 1至999999。

但模数运算下的总和众所周知只是(n(n+1)/2)^2,n是999999。因此，我们的答案是499999500000^2 mod 2453468，其计算结果为2385752。

^{1好吧，差不多。我用Python来做简单的算术。}