Problem

毕达哥拉斯三元组（pythagorean triples）包含有三个整数 $a$, $b$ 和 $c$，满足等式 $a^2+b^2=c^2$。好吧。其实就是人尽皆知的勾股定理。当 $a$, $b$ 和 $c$ 互素时，这个毕达哥拉斯三元组（pythagorean triples）就是 primitive 的。令 $P(n)$ 是满足 $a < b < c \le n$ 的 primitive pythagorean triple 的数目。记 $q$ 和 $p$ 互素，当且仅当 $gcd(q, p) = 1$, $gcd$ 为最大公约数。
(1) 求 $P(10^9)$。
(2) 求 $P(10^{18})$。

Example

$P(20) = 3$，这三个分别是 $(3,4,5)$, $(5,12,13)$ 和 $(8,15,17)$.

Solution

（1） 对于 primitive pythagorean triple，即 $a^2+b^2=c^2, a > 0, b > 0, c > 0$，可以构造成：
$$\left\{\begin{aligned}a &= 2mn\\b &= m^2-n^2\\c &= m^2+n^2\end{aligned}\right.$$
其中，$m > n > 0$，$\gcd(m,n)=1$，$m \bmod 2 \not= n \bmod 2$.

可以直接对 primitive pythagorean triple 进行计数，从 $2$ 到 $\left \lfloor \sqrt{10^9} \right \rfloor$, 遍历 $m$.

如果 $m$ 是偶数，计算 $ \{w | \gcd(m, w) = 1 \text{ and } 0 < w <= \min(\sqrt{10^9-m^2}, x - 1) \}$ 的所有元素个数 $SumA$。

如果 $m$ 是奇数，计算 $\{ w | \gcd(m, w) = 1 \text{ and } 0 < w <= \frac{\min(\sqrt{10^9-m^2}, x - 1)}{2} \}$ 的所有元素个数 $SumB$。

综上，$$\left\{\begin{aligned} P(N) &= SumA + SumB\\N &= 10^9\end{aligned}\right.$$

答案：$P(10^9) = 159154994.$

（2） 由 (1) 知，对于 primitive pythagorean triple，即 $a^2+b^2=c^2, a > 0, b > 0, c > 0$，可以构造成：
$$\left\{\begin{aligned}a &= 2mn\\b &= m^2-n^2\\c &= m^2+n^2\end{aligned}\right.$$
其中，$m > n > 0$，$\gcd(m,n)=1$，$m \bmod 2 \not= n \bmod 2$.

令 $N = 10^{18}$, $N_{s}=\left\lfloor\sqrt{N}\right\rfloor$, $N_{s2}=\left\lfloor\sqrt{\frac{N}{2}}\right\rfloor$

所以需要计算的是 $n \le \text{Min}(m-1,\left\lfloor\sqrt{N-m^2}\right\rfloor)$ 中 $m$ 与 $n$ 的互素对数。

设 $f(m,r)=\sum_{d|m}\mu(d)\frac{r}{d}$ 为在 $[1, r]$ 中和 $m$ 互素的元素个数。可以将 $P(N)$ 分成四部分进行计算再合并。

Part 1

对于 $m$ 是偶数，$2m^2 \le N$，$n \le m-1$ 的情况，因为没有偶数和 $m$ 互素，并且 $m - n$ 为奇数，所以部分和 $m$ 互素的元素个数为 $\varphi(m)$。
$$P_1=\sum_{m=2,even}^{N_{s2}}\varphi(m)=\sum_{d=2,even}^{N_{s2}}\frac{\mu(d)}{d}\sum_{k=1}^{\left\lfloor\frac{N_{s2}}{d}\right\rfloor}kd$$

Part 2

对于 $m$ 是奇数，$2m^2 \le N$，$n \le m-1$ 的情况，因为 $m$ 是奇数，$n$ 肯定是偶数，所以计算的是 $[1,m]$中和 $m$ 互素的偶数的个数，因此也只需要计算 $[1,\frac{m}{2}]$ 中和 $m$ 互素的的元素个数，即 $f(m,\frac{m}{2})$.
$$P_2=\sum_{m=3,odd}^{N_{s2}}\sum_{d|m}\mu(d)\frac{n/2}{d}=\sum_{d=1,odd}^{N_{s2}}\frac{\mu(d)}{d}\sum_{k=1}^{\left\lfloor\frac{N_{s2}}{d}\right\rfloor}\frac{kd}{2}$$

Part 3

对于 $m$ 是偶数，$2m^2 > N$ 的情况，因为 $n \le \left\lfloor\sqrt{N-m^2}\right\rfloor$，对于特定 $m$，在范围$ [1,\left\lfloor\sqrt{N-m^2}\right\rfloor]$ 中与 $m$ 互素的元素个数为 $f(m,\left\lfloor\sqrt{N-m^2}\right\rfloor)$.
$$P_3=\sum_{m=N_{s2}+1,even}^{N_s}\sum_{d|m}\mu(d)\frac{\left\lfloor\sqrt{N-m^2}\right\rfloor}{d}$$
$$P_3=\sum_{d=1,odd}^{N_S}\mu(d)\sum_{k=(N_{s2}+1)/d,even}^{N_s/d}\frac{\left\lfloor\sqrt{N-d^2k^2}\right\rfloor}{d}+\sum_{d=2,even}^{N_S}\mu(d)\sum_{k=(N_{s2}+1)/d,odd}^{N_s/d}\frac{\left\lfloor\sqrt{N-d^2k^2}\right\rfloor}{d}$$

Part 4

对于 $m$ 是奇数，$2m^2 > N$ 的情况，因为 $n \le \left\lfloor\sqrt{N-m^2}\right\rfloor$，类似 Part 2，计算 $[1,\left\lfloor\sqrt{N-m^2}\right\rfloor]$ 中和 $m$ 互素的偶数的个数等价于计算 $[1,\frac{\left\lfloor\sqrt{N-m^2}\right\rfloor}{2}]$ 中和 $m$ 互素的的个数, 即 $f(m,\frac{\left\lfloor\sqrt{N-m^2}\right\rfloor}{2})$.
$$P_4=\sum_{m=N_{s2}+1,odd}^{N_s}\sum_{d|m}\mu(d)\frac{\left\lfloor\sqrt{N-m^2}\right\rfloor/2}{d}$$
$$P_4=\sum_{d=1,odd}^{N_s}\mu(d)\sum_{k=(N_{s2}+1)/d,odd}^{N_s/d}\frac{\left\lfloor\sqrt{N-d^2k^2}\right\rfloor/2}{d}$$

综上，$$\left\{\begin{aligned} P(N) &= P_1 + P_2 + P_3 + P_4.\\N &= 10^{18}\end{aligned}\right.$$

答案：$P(10^{18}) = 159154943091887752.$