今天我们来做一道题目。

输入正整数\(n\)(\(\le 10^{15}\))，求\(x^2+y^2=n^2\)的整数解的个数。

也就是圆心为原点，半径为\(n\)的圆上整点的数量。

为了得到更普遍的结论，我们改为\(x^2+y^2=n\)来做。

---

我们引入一个概念，叫做

【定义1】高斯整数：形如\(a+bi\)的数称为高斯整数，其中\(a,b\in Z,i=\sqrt{-1}\)。

于是就转化为了求\((a+bi)(a-bi)=n\)中\(a,b\)的数量。

注意到\(n,a+bi,a-bi\)都是高斯整数，就联想到对高斯整数\(n\)进行质因数分解。

【定义2】高斯素数：高斯整数中，不能分解为两个高斯整数的乘积（\(1,-1,i,-i\)除外）的，称为高斯素数。

至于为什么\(1,-1,i,-i\)除外，就像整数分解中\(1,-1\)除外一样，因为这些东西是单位元，对分解形式没有什么大的影响，所以就去除了。

如何对整数\(n\)进行高斯素数的分解呢？注意到\(n=p_1p_2\ldots p_k\)有唯一分解形式，只要考虑质数\(p\)如何进行高斯素数的分解。于是就有了

【定理1】（费马二平方和定理） 对于质数\(p\)，若\(p\equiv 1(\mathrm{mod} \ 4)\)或\(p=2\)，则\(x^2+y^2=p\)有一个正整数解；若\(p\equiv 3(\mathrm{mod} 4)\)，则\(x^2+y^2=p\)无正整数解。

举个栗子，\(5=(2+i)(2-i),17=(4+i)(4-i),13=(3+2i)(3-2i)\)，而\(3,7,31\)这些素数无法分为两个共轭的高斯整数的乘积。

（这个定理的证明被鸽掉了，大家当结论用吧）

也就是说，\(25=5^2=(2+i)(2-i)(2+i)(2-i)\)，那么如何计算\(25=(a+bi)(a-bi)\)的解的数量呢？我们把质因子分为两个元素个数相等的可重集合\(A,B\)，其中满足\(z\in A\Rightarrow \bar{z}\in B\)，也就是\(A,B\)中的元素对应互相共轭，则令\(Z=\prod_{z\in A}z\)，则\(\bar{Z}=\prod_{z\in A}\bar{z}=\prod_{z\in B}z\)，所以\(n=Z\times \bar{Z}\)，令\(a+bi=Z\)即可。

也就是说一种\(A,B\)的分配方法对应了一组整数解，注意到如果\(A\)中有\(a\)个\(2+i\)，那么\(B\)中有\(2-a\)个\(2+i\)，有\(a\)个\(2-i\)，\(A\)中有\(2-a\)个\(2+i\)，所以共有3组整数解。。。

吗？

枚举一下就发现实际上是\(12\)组整数解，因为上面我们将\(1,-1,i,-i\)除去了，实际上我们可以对其中一个数乘上\(1,-1,i,-i\)，另一个数对应地乘上\(1,-1,-i,i\)，于是还应该乘上4倍。

再来看看\(75=3*5^2=3(2+i)(2-i)\)，发现无论\(3\)放到哪里都是不行的，因为对面也要有一个\(3\)。所以\(x^2+y^2=75\)没有整数解。

再来看看\(50=2*5^2=(1+i)(1-i)(2+i)(2-i)\)，根据刚才的计算方法，我们可以在左边放\(a\)个\(1+i\)，\(b\)个\(2+i\)，其中\(0\le a,b\le 1\)，则有\(4\)种，再乘上\(4\)就是\(16\)个整数解。。。

吗？

枚举一下就发现实际上是\(8\)组整数解，因为上面我们要乘上\(4\)是因为可以对其中的数乘上\(1,-1,i,-i\)，但是我们发现\(1+i=i(1-i)\)，所以\(1+i\)和\(1-i\)放在哪里并没有关系，所以\(n\)中\(2\)的质因子个数对答案没有影响。应该忽略就可以了。

---

现在我们总结一下\(n=2^ap_1^{a_1}p_2^{a_2}\ldots p_k^{a_k}\)，则根据上面的讨论，\(2^a\)对答案没有贡献，如果\(p_i\equiv 1(\mathrm{mod} \ 4)\)则对答案有\(a_i+1\)的贡献，如果\(p_i\equiv 3(\mathrm{mod} \ 4)\)，若\(2|a_i\)则对答案没有贡献，否则对答案有\(0\)的贡献（无解），乘起来得到的再乘上\(4\)就是最后答案。

现在我们已经能做出来这道题了，对\(n^2\)进行质因数分解，然后直接套公式就可以做出来了。

---

众所周知，与圆周率\(\pi\)有关的有一堆的公式，我们今天算的是圆上的整点个数，所以我们讨论一下它和\(\pi\)的关系。

注意到半径为\(R\)的圆面积\(\pi R^2\)近似于内部的整点个数，我们用这个来计算\(\pi\)，而且\(R\)越大算的就越精确（误差是\(O(R)\)级别而面积是\(O(R^2)\)级别的）。

虽然上面的结论已经非常简洁了，但是做这道题我们还需要再进行简化一下。我们引入

【定义3】我们定义数论函数\(\chi(n)\)，其中
\[ \chi(n)=\begin{cases}1 & (n\equiv 1(\mathrm{mod} \ 4)) \\ -1 & (n\equiv 3(\mathrm{mod} \ 4)) \\ 0 & (2|n)\end{cases} \]
所以\(\chi(n)\)是一个完全积性函数，而且
\[ \begin{aligned} \chi(1)+\chi(5)+\chi(5^2)+\chi(5^3)&=4 \\ \chi(1)+\chi(3)+\chi(3^2)+\chi(3^3)&=0 \\ \chi(1)+\chi(3)+\chi(3^2)+\chi(3^3)+\chi(3^4)&=1 \\ \chi(1)+\chi(2)+\chi(2^2)+\chi(2^3)&=1 \end{aligned} \]
整明白点儿啥没？

\(x^2+y^2=n\)的整数解的数量（除以4）为
\[ \begin{aligned} &(\chi(1)+\chi(p_1)+\chi(p_1^2)+\ldots+\chi(p_1^{a_1}))\times \\ &(\chi(1)+\chi(p_2)+\chi(p_2^2)+\ldots+\chi(p_2^{a_2}))\times \\ &\ldots \\ &(\chi(1)+\chi(p_k)+\chi(p_k^2)+\ldots+\chi(p_k^{a_k})) \\ =&\sum_{0\le b_i\le a_i}\prod_{i=1}^k\chi(p_i^{b_i}) \\ =&\sum_{0\le b_i\le a_i}\chi(\prod_{i=1}^k p_i^{b_i}) \\ =&\sum_{d|n}\chi(d) \end{aligned} \]
【定理2】\(x^2+y^2=n\)的整数解的数量为\(4\sum_{d|n}\chi(d)\)。

圆内整点的数量实际上就是同心且比它小的所有圆经过的整点数量，我们设\(R^2=n\)。
\[ \begin{aligned} \frac{\pi}{4}&=\lim_{n\rightarrow +\infty}\frac{\sum_{i=1}^{n}\sum_{d|i}\chi(d)}{n} \\ &=\lim_{n\rightarrow +\infty}\frac{\sum_{d=1}^n\chi(d)\frac{n}{d}}{n} \\ &=\lim_{n\rightarrow +\infty}\sum_{d=1}^n\frac{\chi(d)}{d} \\ &=1-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}+\frac{1}{9}-\frac{1}{11}+\ldots \end{aligned} \]
整明白点儿啥没？