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) \to ((a_1c+b_1d),(a_1d-b_1c)) or ((a_1c-b_1d),(a_1d+b_1c))$
$((a_2,b_2),p) \to ((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
Fermat Sum of Two Squares Calculator
OLD blog
f(N) = 在(过(0,0),(N,0),(0,N)的圆)上的整点个数
求 sum{f(i=1->10^11) == 420}
解
显然 暴力不可取:-)
也就是 $(x-\frac{N}{2})^2+(y-\frac{N}{2})^2 = 2(\frac{N}{2})^2$，其中如果N是基数两侧同时乘以4
整体还是 x^2+y^2=2z^2 的形式
回想75的 勾股数的证明步骤
拆分基本满足表达式和通过倍数生成的。下面只考虑基本的满足表达式的
gcd(x,y)=gcd(y,z)=gcd(x,z) = 1 两两互质
因为$x,y$是奇数所以是$4k+1$ 或$4k+3$ 平方后为$4m+1$,和为$ 4n+2 = 2(2n+1)$
$(x,y,z) = 奇,奇,奇$ ,注意到表达式的几何意义完全对称，因此只考虑 (x>0,y>0,z>0),因为轴上一定无整点，所以整点个数，为4倍考虑的区域
$(x-z)(x+z)=(z-y)(z+y)$
然后注意到|x|=|y|=z在上面不会被 m,n表示，因为实际表示分母为零，而实际上在几何上就是 题目描述的$(0,0),(0,N),(N,0),(N,N)$
令最简分数 $\frac{m}{n} = \frac{x-z}{z-y} = \frac{z+y}{z+x}$,即$gcd(m,n) = 1$,且$m>0,n>0$
$\frac{m}{n} + 1 = \frac{x-y}{z-y}$
$\frac{n}{m} - 1 = \frac{x-y}{z+y}$
$\frac{n}{m+n} + \frac{m}{n-m} = \frac{n^2+m^2}{n^2-m^2} = \frac{2z}{x-y}$
$\frac{m}{n-m} - \frac{n}{m+n} = \frac{m^2+2mn-n^2}{n^2-m^2} = \frac{2y}{x-y}$
$x-y = n^2-m^2$
$2y = m^2 - n^2 + 2mn$
$2z = n^2 + m^2$
$y = \frac{m^2 - n^2 + 2mn}{2}$
$x = \frac{n^2 - m^2 + 2mn}{2}$
$z = \frac{m^2 + n^2}{2}$
若 $m,n$全奇数，上述$x,y,z$ 根据mod4,显然也全为奇数
若 $m,n$一奇一偶，上述$x,y,z$表达式同时乘2,显然也全为奇数
因为$gcd(m,n) = 1$，根据gcd运算法则也可得到$x,y,z$两两互质
综上每个$x^2+y^2=2z^2$可以根据$m,n$表述成上述式子,每组$gcd(m,n) = 1$也可以生成$x^2+y^2=2z^2$
回到题目
看$z$的表达式 说明$m,n < \sqrt{2 * 10^{11} } = 447213.5954….$
再来对称性 只考虑 m > n
$f(p)$表示 直接达成p的方案数
易知 $f(偶数) = 0$, $f(1) = 4$,$n > (\sqrt{2}-1)m$
$ans(k) = sum(f(p)), k%p = 0$
平方和 + 因子计算, 就要$O(\sqrt{N}^3 = N^\frac{3}{2})$,
很明显 时间复杂度降低了, 但是依然是无法暴力出来的
因为上面的式子，会想到莫比乌斯反演，但暂时没想到更深的。
参考
发现了个这个 https://www.hackerrank.com/contests/projecteuler/challenges