计算i^2453467 mod 2453468 for 1<=i<=999999的和（^表示幂）
Calculate the sum of i^2453467 mod 2453468 for 1<=i<=999999 (^ means power)
如何在更短的时间内高效地解决这类问题？我曾尝试在 Python 中解决这个问题，但它花费了很多时间。我一直在想，也许 ^ 的意思是 xor 而不是权力，但根据他们的说法，它是权力。这是一个编码竞赛的问题。
https://en.wikipedia.org/wiki/Modular_exponentiation
关注Memory efficient的计算方法。实施起来应该非常简单。
在python代码中
answer = 0
for i in range (1, 1000000):
answer += pow(i, 2453467, 2453468)
print answer % 2453468
速度好像够快
一般情况下，是的，你最好使用模幂，这确实很简单，如@F.Ju所示。然而，通过一点数学你可以用笔和纸完全计算出总和1.
需要注意的关键是指数 (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）中，有 3 种数不与 2453468 互质。一种是613367，对于每个k.
证明613367^(2k+1) mod 2453468=613367相对容易
另一种是可以被 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整除的数，可以和前一类一样对待。
因此，我们有
For every x from 1 to 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做简单的算术。
如何在更短的时间内高效地解决这类问题？我曾尝试在 Python 中解决这个问题，但它花费了很多时间。我一直在想，也许 ^ 的意思是 xor 而不是权力，但根据他们的说法，它是权力。这是一个编码竞赛的问题。
https://en.wikipedia.org/wiki/Modular_exponentiation
关注Memory efficient的计算方法。实施起来应该非常简单。
在python代码中
answer = 0
for i in range (1, 1000000):
answer += pow(i, 2453467, 2453468)
print answer % 2453468
速度好像够快
一般情况下，是的，你最好使用模幂，这确实很简单，如@F.Ju所示。然而，通过一点数学你可以用笔和纸完全计算出总和1.
需要注意的关键是指数 (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）中，有 3 种数不与 2453468 互质。一种是613367，对于每个k.
613367^(2k+1) mod 2453468=613367相对容易
另一种是可以被 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整除的数，可以和前一类一样对待。
因此，我们有
For every
xfrom 1 to 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做简单的算术。