Project Euler 120

题目

Square remainders

Let \(r\) be the remainder when \((a-1)^n + (a+1)^n\) is divided by \(a^2\).

For example, if \(a = 7\) and \(n = 3\), then \(r = 42: 6^3 + 8^3 = 728 \equiv 42 \bmod 49\). And as \(n\) varies, so too will \(r\), but for \(a = 7\) it turns out that \(r_{\max} = 42\).

For \(3 \le a \le 1000\), find \(\sum r_{\max}\).

二项式定理

二项式定理，即\(n\)次方二项式\((a+b)^n\)的展开式：

\[(a+b)^n=\sum_{i=0}^n\dbinom{n}{i}a^ib^{n-i}\]

解决方案

设\(r(a,n)=((a-1)^n+(a+1)^n) \% a^2\)。

根据二项式定理，对\(a^2\)取模后，二项式展开式中\(a\)的次数为\(2\)及以上的项不考虑，只考虑\(a\)的次数为\(0\)或\(1\)的项。

因此，满足下式：

\(r(a,n) \equiv \dbinom{n}{1}a\cdot(-1)^{n-1}+\dbinom{n}{0}(-1)^n+\dbinom{n}{1}a\cdot 1^{n-1}+\dbinom{n}{0}1^n\equiv an+1+an\cdot(n-1)^n+(-1)^n\pmod{a^2}\)

可以写成：

\[ r(a,n)= \left \{\begin{aligned} &2 & & \text{if}\quad n \equiv 0 \pmod 2 \\ &2an \%a^2 & & \text{else} \end{aligned}\right. \]

为使得\(r(a,n)\)最大，故不考虑\(n\)为偶数的情况。那么此时可以写成\(r(a,n)=a\cdot (2n \% a)\)。

值\(2n\%a\)需要尽可能接近\(a\)。由于\(2n\)为偶数，因此当\(a\)为偶数时，\(\gcd(a,2)=2\)，因此\(2n\%a\)最大能只能取到\(2\)的倍数\(a-2\)，而当\(a\)为奇数时，\(\gcd(a,2)=1\)，\(2n\%a\)最大可以取到\(1\)的倍数\(a-1\)。

因此有：

\[ r_{\max}(a)= \left \{\begin{aligned} &a(a-2) & & \text{if}\quad a \equiv 0 \pmod 2 \\ &a(a-1) & & \text{else} \end{aligned}\right. \]

代码

N = 1000
ans = 0
for a in range(3, N + 1):
    if a & 1:
        ans += a * (a - 1)
    else:
        ans += a * (a - 2)
print(ans)