题目120：求(a-1)^n + (a+1)^n除以a^2的最大余数
本帖最后由 永恒的蓝色梦想 于 2020-7-2 18:05 编辑Square remainders
Let r be the remainder when (a-1)n + (a+1)n is divided by a2.
For example, if a = 7 and n = 3, then r = 42: 63 + 83 = 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)n + (a+1)n 除以 a2 所得的余数
比如，如果 a=7，n=3，则 r =42: 63+83=728 42 mod 49.n 变化的话，r 的值也会随着变化，但是我们发现，当 a=7 时，r 取到最大值 42。
请求出 a 从 3 到 1000 所得的 r 的最大值之和。 '''
(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)^nmod 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
页:
[1]