题目120：求(a-1)^n + (a+1)^n除以a^2的最大余数

欧拉计划

Square remainders

Let r be the remainder when (a-1)ⁿ + (a+1)ⁿ is divided by a².

For example, if a = 7 and n = 3, then r = 42: 6³ + 8³ = 728 ≡ 42 mod 49. And as n varies, so too will r, but for a = 7 it turns out that rmax = 42.

For 3 ≤ a ≤ 1000, find ∑ ^rmax.

题目：

设 r 为 (a-1)ⁿ + (a+1)ⁿ 除以 a² 所得的余数

比如，如果 a=7，n=3，则 r =42: 6³+8³=728 42 mod 49.  n 变化的话，r 的值也会随着变化，但是我们发现，当 a=7 时，r 取到最大值 42。

请求出 a 从 3 到 1000 所得的 r 的最大值之和。

gunjang

'''
(a+1)^n = 0Cn*a^n+1Cn*a^(n-1)....(n-2)Cn*a^2+(n-1)Cn*a+1
when n>=2
(a+1)^n mod a^2 == (n-1)Cn*a+1 = 1Cn*a+1=n*a+1

(a-1)^n = 0Cn*a^n-1Cn*a^(n-1).... (-1)^x*(n-2)Cn*a^2+(-1)^x*(n-1)Cn*a+(-1)^x*1
(a-1)^n mod a^2 == (n-1)Cn*a+1 = (-1)^(n-1)1Cn*a+(-1)^n*1= -n*a+1 (n is even) or n*a-a (n is odd)

n = 1 2a/a^2 ===2na
so
if odd(n): (a+1)^n+(a-1)^n  mod a^2 === 2na mod a^2  ===> max remainder is (nearest even number of a)*a
if even(n):  === 2 mod a^2
'''
def rmax(a):
        remainder = max(2%a, ((a-1)//2)*2*a) #nearest even number of a
        return remainder

s = 0
for a in range(3, 1001):
        s += rmax(a)
print(s) #333082500

答案是333082500