给定$r$，求满足$x^2+y^2=r^2$的整数对$(x,y)$个数量。
链接
Luogu P2508
BZOJ 1041
CodeVS 1867
前置知识
首先引入虚数单位$\mathrm{i}$，表示$\sqrt{-1}$，将$a+b\mathrm{i},a,b\in\mathbb{R}$型的数称为复数（其中$a\in\mathbb{R}$表示$a$为实数）。
所以说可以规定一些运算。
$a+b\mathrm{i}\pm c+d\mathrm{i}=(a\pm b)+(c\pm d)\mathrm{i}$
$(a+b\mathrm{i})(c+d\mathrm{i})=(ac-bd)+(ad+bc)\mathrm{i}$
其中，称$a+b\mathrm{i}$的复共轭为$a-b\mathrm{i}$。
每一个坐标$(x,y)$，又可以唯一对应到一个复数$x+y\mathrm{i}$，于是将这种一个坐标表示一个复数的平面直角坐标系叫做复平面。
对于复平面上的格点$(x,y)$，可以对应到复数$x+y\mathrm{i}$，将这类复数叫做高斯整数。
说白了，高斯整数就是满足$a,b$是整数的$a+b\mathrm{i}$型数。
而不能再次被分解的数就是高斯素数。
比如说，$5$不是高斯素数，因为$5=5+0\mathrm{i}=(2+\mathrm{i})(2-\mathrm{i})$，而分解出的$2+\mathrm{i}$和$2-\mathrm{i}$都是高斯素数。
题解
一道码量不长，但是数学知识需求挺多的一道题。
先转换一下所给的方程，改成$x^2-(y\mathrm{i})^2=r^2$。
拆开可得$(x+y\mathrm{i})(x-y\mathrm{i})=r^2$。
而两个括号内互为复共轭，所以只需要解决这个问题，即有多少个$x+y\mathrm{i}$使得它成它的复共轭为$r^2$。
这里举个栗子，比如说手玩$r=5$的情况，要先将$r^2$拆成高斯素数的乘积。
$25=5^2=(2+\mathrm{i})(2-\mathrm{i})(2+\mathrm{i})(2-\mathrm{i})$
在将这些高斯素数分成两列，其中第一列的第$n$个数和第二列的第$n$个数互为复共轭，最后算出来有多少种组合方式。
但是这些组合方式满足左边的乘积与右边的乘积互为复共轭吗？
答案是显然的，先证明两个高斯整数的乘积与它们的复共轭的乘积互为复共轭。
考虑这两个数的乘积，$(a+b\mathrm{i})(c+d\mathrm{i})=(ac-bd)+(ad+bc)\mathrm{i}$。
它们的复共轭的乘积，$(a-b\mathrm{i})(c-d\mathrm{i})=(ac-bd)-(ad+bc)\mathrm{i}$。
啊哈！它们正好互为复共轭，所以左边的乘积与右边的乘积互为复共轭。
但是，还不够。要把答案乘上$4$才行，因为两列数的乘积可以同时乘上$1$或$-1$，或一个乘以$\mathrm{i}$，另一个乘以$-\mathrm{i}$都不改变两列乘起来后两个数的乘积，所以有$4$种变换，所以算出来是$12$。
现在来看一般情况。对$r^2$做质因数分解，有$r^2={p_1}^{r_1}{p_2}^{r_2}\cdots {p_k}^{r_k}$。
假设现在考虑到$p_i$了（这个$i$与虚数单位的字体不一样），那么……
如果$p_i\equiv 1\pmod 4$，那么这个可以分解成两个高斯素数的乘积。这个因子对格点数目点的影响为$r_i+1$，因为可以在左边放$0,1\cdots r_i$个分解后的高斯素数中的一种。
如果$p_i\equiv 3\pmod 4$，那么$p_i$本身是高斯素数，对分解的贡献取决于$r_i$，如果$r_i$是奇数，那么这个多出来的因子没地方放，它会使得两边不平衡，没有格点，否则，它可以放两边，对格点个数没有贡献。
如果$p_i$为$2$，那么有$2=(1+\mathrm{i})(1-\mathrm{i})$，而这两个复数刚好是旋转$90^{\circ}$的，所以变换少了$2$种，但是带来$2$中组合，对格点个数没有贡献。
所以，这个算法只需要分解质因数，然后判断即可。
不懂的可以看看这个视频
代码
1 |
|