project euler 233 (直角三角形)
题目
https://projecteuler.net/problem=233
题意
$f(N) = $ 和 $(0,0)(0,N),(N,0),(N,N)$ 共圆的整点的个数
例如 $f(10000) = 36$
求 $1 \leq i \leq 10^{11}$ 使得$f(i)=420$ 的所有$i$的和
题解
我目前想到的
对称性
首先 圆上的点 (x,y) 满足
$(x-\frac{N}{2})^2+(y-\frac{N}{2})^2 = \frac{N^2}{2}$
根据对称性
我们只用考虑 $\frac{N}{2} < x < y $ 的个数，然后乘8 加4(对角线的点)
$420 = 52 \cdot 8 +4$
所以这里我们其实 需要求满足上述两个条件的整点 方案为52的即可
奇偶
若 N 为奇数
$(2x-N)^2+(2y-N)^2 = 2N^2$, 要解的方程是$a^2+b^2=2c^2, (0 < a < c < b )$且$a,b,c$均为奇数的形式
若 N 为偶数，令 $N=2k$
$(x-k)^2+(y-k)^2 = 2k^2$, 要解的方程是$a^2+b^2=2c^2$ 的形式
考虑 到$\bmod 4$ 的情况
$ 0^2 = 0 \bmod 4 $
$ 1^2 = 1 \bmod 4 $
$ 2^2 = 0 \bmod 4 $
$ 3^2 = 1 \bmod 4 $
所以 $(a,b,c)$ 同奇偶
因此如果k仍然是偶数，则继续除以2，反复迭代直到c为奇数
最终我们只用考虑 奇数的形式
也得到结论如果N是偶数，那么$f(N) = f(\frac{N}{2})$
公约数
若 $gcd(a,b) = k > 1$，那么显然 $gcd(a,c) = k$
所以$(a,b,c)$同时除以$k$依然成立
同理$(a,c),(b,c)$ 只用考虑 $(a,b,c)$ 两两互质，非互质的是通过互质的倍数得到的
令 $g(c) = $ 使得 $a^2+b^2=2c^2 ,(0 < a < c < b),(a,b,c)$ 两两互质 且 全为奇数(废话，可以不加这条因为是等式的结论) 的方案数
$c$是奇数时 $ f(c) = \sum_{c = 0 \bmod i}g(i)$
变形 与 直角三角形
$a^2+b^2=2c^2, (0 < a < c < b )$且$a,b,c$均为奇数的形式
思路1
$b^2 - 2c^2 = -a^2$ 然后 佩尔方程类似的去解
如果能得到不同a的初始解，剩余的解很容易得到，但是初始解还是只能枚举
思路2
令$d = \frac{a+b}{2}$,$e = \frac{b-a}{2}$
则$d,e$为整数且奇偶互异,
带入 $(d-e)^2+(d+e)^2=2c^2$
即$d^2+e^2=c^2$
这和 直角三角形的基础解是一一对应的,(直角三角形基础解的讲解 见 PE075 的题解)
所以 $k(a,b,c)$ 与 $k(d,e,c)$ 一一对应
所以 问题变成了
c 为直角三角形边 恰好 52 种的方案数
计算方案数 与 方案数性质
根据 直角三角形基础解的性质
若 满足$c = k (m^2+n^2), (m>n>0) , (m+n)=1 \bmod 2$
则 c 是一个直角三角形的斜边
问题是 数量级在$10^{11}$ 虽然 m 和n 都不到$10^6$了，但是基于时间和空间 依然 无法暴力
费马平方和定理
奇质数能表示为两个平方数之和的充分必要条件是该质数被4除余1
https://yexiaorain.github.io/Math/Fermat_s_two_square_theorem/
回到题目
我们之前的结论是：
若 满足$c = k (m^2+n^2), (m > n > 0) , (m+n)=1 \bmod 2$
则 $c$ 是一个直角三角形的斜边, 求有52个解的所有的$c$的和
现在有的理论基础是：
若$a,b$ 互质,则$a^2+b^2$所有质因子都是$4n+1$的形式, 且这些质因子自身唯一分解
反过来$4n+1$的质数的乘积 能表示成 $a^2+b^2$，但是可能$a,b$不互质, 例如$5^4 = 5^2(5^2) = 5^2(3^2+4^2)=15^2+20^2$
所以上面的一个数$c$质因数分解,则 模4余3的质因子和2全在k中,模4余1的因子可以在k中也可以不在k中
$k(m^2+n^2) = c = 2^{c_1} p_1^{a_1} \cdots p_r ^{a_r} q_1^{b_1} \cdots q_s ^{b_s}$
$k$是$2^{c_1}q_1^{b_1} \cdots q_s ^{b_s}$ 的倍数
$p_1^{a_1} \cdots p_r ^{a_r}$是$(m^2+n^2)$ 的倍数
表示方法来源的唯一性, 一个仅由4n+1素数乘积构成的数的平方数分解，全部恰好由其任意一个素数的表示法与剩余部分的表示法生成
我们下面只关心$X = m^2+n^2 = p_1^{d_1} \cdots p_r ^{d_r}$的部分, 这里幂次用d区别了上面的a，表示确定选择的部分，仅仅是上面a的部分约数即可
任意拆一个质因子
$X = (p_1^{d_1} \cdots p_i^{d_i-1}\cdots p_r ^{d_r})\cdot p_i$
已知对于左侧任意一个表示法$a^2+b^2$, 和 右侧的一个唯一的表示法$c^2+d^2$
由费马平方和定理第一条, 可以对$X = (a^2 + b^2)(c^2 + d^2) = (ac+bd)^2+(ad-bc)^2 = (ac-bd)^2+(ad+bc)^2$
也就是 对于给定$(a,b), p $ 能产生考虑正负的16个点，这8个点一组，每组内的点按坐标轴和对角线对撑
$((a,b), p) => (\pm(ac+bd),\pm(ad-bc)) or (\pm(ac-bd),\pm(ad+bc))$ 或交换横纵坐标
反过来，考虑$X = e^2+f^2 = $ 的一个任意的表示法
$X = e^2+f^2 = (p_1^{d_1} \cdots p_i^{d_i-1}\cdots p_r ^{d_r})\cdot (c^2+d^2)$
由上面费马平方和定理第二条
$(p_1^{d_1} \cdots p_i^{d_i-1}\cdots p_r ^{d_r}) = (\frac{ec+fd}{p})^2+(\frac{ed-fc}{p})^2$ 能表示成整数的平方和 或 $= (\frac{ec-fd}{p})^2+(\frac{ed+fc}{p})^2$能表示成平方和的倍数
所以，至少有一个拆解
如果是第一个
$((\frac{ec+fd}{p})^2+(\frac{ed-fc}{p})^2)(c^2+d^2) = (c\frac{ec+fd}{p}+d\frac{ed-fc}{p})^2+(c\frac{ed-fc}{p}-d\frac{ec+fd}{p})^2 = (\frac{e(c^2+d^2)}p)^2+(\frac{-f(c^2+d^2)}p)^2 = e^2+f^2$
第二个同理可证，说明了刚好为逆运算
也就说明了，对于每一个$X$的表示，其所有的可行拆解对应逆运算能得到$X$对应的表示,那么在考虑所有正负的情况下，通过 费马定理第一条，能不漏的计算出$X$的所有表示
然后整理一下值，我们发现$(\pm a,\pm b), (\pm b,\pm a)$ 所产生的16个点不会因为$a,b$的正负和顺序受到影响
所以我们仅去考虑$0 < a < b$, 也就是x正向轴，和y=x正向 之间区域的点作为a,b ，同时产生的点也仅考虑在这个区域的点。
那么有，根据费马定理的第一步，每组$((a,b),p)$ 产生两个新的点
点的计数(TODO
这样保证了点的不漏,每多一个质数，原来的一个点就能产生新的两个点，数量显然是$2^{d_1+d_2+\cdots+d_r-1}$
接下来考虑不重复计数
$((a,b), p = c^2+d^2) => ((ac+bd),(ad-bc)) or ((ac-bd),(ad+bc))$
若 $ac+bd = ad+bc $, 即$(a-b)(c-d) = 0$ 不会成立
若 $ac+bd = | ac - bd | $, 即$bd=0$或$ac =0$ 不会成立
所以 对于一个$((a,b),p)$ 产生的两个点必不相同
考虑不同的$a,b$, $a_1^2+b_1^2 = a_2^2+b_2^2$
$((a_1,b_1),p) => ((a_1c+b_1d),(a_1d-b_1c)) or ((a_1c-b_1d),(a_1d+b_1c))$
$((a_2,b_2),p) => ((a_2c+b_2d),(a_2d-b_2c)) or ((a_2c-b_2d),(a_2d+b_2c))$
若 $a_1c+b_1d = a_2c+b_2d$,
?????????????????????
目前看 相关资料，表示Dummit & Foote, 3rd ed., p 291有相关证明
点的计数
引理定义们
除法: 对于所有$a,b\in \mathbb{Z},b \neq 0$,有唯一$q,r\in \mathbb{Z}, 0\leq r < |b|$ 使得 $a=bq+r$
整除: 对于$a,b\in Z$ $a$是$b$的除数，当存在一个整数$x$, 使得$ax = b$, 写作$a \mid b$,不整除写作$a \nmid b$
恒成立的整除: $1 \mid a,-1 \mid a, a \mid a, -a \mid a$
质数: 仅有上述恒成立的整除关系，且为正，非1
互质: $a,b$ 互质，当它们公共的除数，仅有正负1
最大公约数: $gcd(a,b)$ 所有a和b共有的约数中最大的一个
合数: $a = p_1\cdot p_2 \cdots p_k$, 唯一表示
Ref
Brahmagupta-Fibonacci Identity
Fermat’s theorem on sums of two squares