120. 平方余数(Square remainders)

\(r\)\((a-1)^n+(a+1)^n\)除以\(a^2\)的余数,比如当\(a=7\)\(n=3\)\(r=42\),因为:

$$ 6^3+8^3=728\equiv42(mod\ 49) $$
\(n\)变化的时候,\(r\)也会变化,但是当\(a=7\)\(r\)的最大值\(r_{max}=42\)。对于\(3\le a\le1000\),求\(\sum{r_{max}}\)

分析:这道题实际上是一个纯粹的数学问题,并不需要编程解决。首先我们需要研究一下被除数,根据二项式定理有:

$$ (a-1)^n+(a+1)^n=\sum_{i=0}^n{C_{n}^{i}a^i\left( 1 \right) ^{n-i}+\sum_{i=0}^n{C_{n}^{i}a^i\left( -1 \right) ^{n-i}}}=\sum_{i=0}^n{C_{n}^{i}a^i\left[ \left( -1 \right) ^{n-i}+1 \right]} $$

对于上式中的\(a^i\)项,当\(i\ge2\)时必然可以整除\(a^2\),则不会对余数有贡献,需要考虑的是只是\(i\)等于一和等于零的情况,把这两项单独提出来,有:

$$ \sum_{i=0}^1{C_{n}^{i}a^i\left[ \left( -1 \right) ^{n-i}+1 \right]}=\left[ \left( -1 \right) ^n+1 \right] +\left[ \left( -1 \right) ^{n-1}+1 \right] na $$

则当\(n\)是偶数时,上式恒等于二;当\(n\)为奇数时,上式等于\(2na\)。因此当\(n\)为偶数时,原式除以\(a^2\)的余数恒为二,不可能取得最大值。我们只需要考虑\(n\)为奇数的情况,也即求\(2na\)除以\(a^2\)的余数的最大值。根据求余运算的相关性质,我们设\(a^2\)的整数倍为\(ka^2\),则只有\(2na<ka^2\)且两者之间距离最小时这个余数才会取得最大值。

我们以题目中的说明为例,当\(a=7\)时要求\(r_{max}\),即求\(14n\)除以\(49\)的余数的最大值,也就是求\(49k-14n\)的最小值,这个式子实际上可以看成一个线性丢番图方程,则根据求解线性丢番图方程的相关知识,我们知道形如\(ax+by\)的式子可以形成的最小正整数为\(gcd(a,b)\),则同理对于式子\(49k+14(-n)\)可以形成的最小正整数为\(gcd(49,14)=7\),则此时的余数为\(49-7=42\)正是余数的最大值。

因此要求\(ka^2-2an\)的最小值,即要求\(gcd(a^2,2a)\)。当\(a\)是一个偶数,则\(a^2\)也是一个偶数,\(2a\)显然也为偶数,则两者的公因子除开\(a\)以外还包含\(2\),则\(gcd(a^2,2a)=2a\),此时余数的最大值应该为\(a^2-2a\);反之 ,当\(a\)为一个奇数,则\(a^2\)也是一个奇数,此时\(gcd(a^2,2a)=a\),此时余数的最大值为\(a^2-a\)。因此有:

img

当然,我们也可以写一小段代码计算出结果,如下:

# time cost = 617 µs ± 1.28 µs

def main():
    even = [a**2-2*a for a in range(3,1001) if a%2==0]
    odd = [a**2-a for a in range(3,1001) if a%2==1]
    ans = sum(even) + sum(odd)
    return ans