题解 P1214 【[USACO1.4]等差数列 Arithmetic Progressions】

p878567 · 2017-12-30 15:35:31 · 题解

有一种特殊的思路：（证明n>=4时，b=4k）。

过程：设p=a^2+b^2。

1.a,b为偶数。设a=2m,b=2n，则p=4(m^2+n^2)。

2.a,b一奇一偶。不妨令a=2m+1,b=2n，则p=4(m^2+n^2+m)+1.

3.a,b为奇数。设a=2m+1,b=2n+1，则p=4[m(m+1)+n(n+1)]+2.

由于m,m+1中有1个偶数，故m(m+1)为偶数，同理，n(n+1)为偶数，即m(m+1)+n(n+1)为偶数，有p=8l+2\text{（}l\text{为自然数）}.

即p\bmod 4\neq 3.

即n>=4时，b为偶数.

若4\nmid b，则a为偶数。由于能写成8l+6的形式的数无法写生两个完全平方数的和（8l+6=4(2l+1)+2，即能8l+6写成4l+2的形式，但已证能写成4l+2形式的数一定不是完全平方数），故a为奇数，矛盾。

即4\mid b。

直接搜索，b要4个4个加（n=3时暴力搜索，有答案不超过10000个的限制，因此m很小）。