python - 计算 1<=i<=999999 的 i^2453467 mod 2453468 的总和（^ 表示幂）

Question

如何在更短的时间内有效地解决这类问题？我试图在 Python 中解决这个问题，但它需要很多时间。我一直在想这可能^意味着 xor 不是权力，但据他们说这是权力。这是一个编码竞赛的问题。

Answer 1

在一般情况下，是的，您应该更好地使用模幂运算，这确实很简单，如@F.Ju 所示。但是，通过一些数学运算，您可以用笔和纸¹完全计算总和。

需要注意的关键是指数 ( 2453467) 非常接近模数 ( 2453468)，这需要更简单的表示x^2453467 mod 2453468。确实，如果 2453468 是素数，那么x^2453467 mod 2453468总是1根据费马小定理。

虽然它不是素数，但它有一个非常简单的表示2*2*613367。所以我们可以记住欧拉定理，并发现phi(2453468)等于1226732，等等2453467=2*phi(2453468)+3。因此，x对于与 相对质数的每一个，2453468我们有x^1226732=1，并且2453467，1226732*2+3我们有x^2453467 mod 2453468=x^3 mod 2453468。

然后让我们考虑与 不互质的数2453468。在超出范围（1 到 999999）内，有 3 种数字与 不互质2453468。一个是，而且对于每个人613367来说都比较容易证明这一点。613367^(2k+1) mod 2453468=613367k

另一种是能被 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

从x1 到 999999。

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

^{1 嗯，差不多。我用 Python 做简单的算术运算。}

Answer 2

在python代码中

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

速度似乎足够快

Answer 3

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

专注于内存高效的计算方法。应该很容易实现。