自动搬运

查看原文

来自洛谷，原作者为

	emptysetvvvv 这里埋葬着一位 OIer 的青春

搬运于2025-08-24 21:38:28，当前版本为作者最后更新于2020-03-13 14:17:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

背景

深夜，一位退役 OIer 正坐在电脑前恰着零食喝着快乐水逛着B站。

突然，emptyset 发现了一则十分通俗易懂并且相当有趣的双语科普视频。

emptyset 总记得见过这问题，迅速打开洛咕一看，我靠，何止是见过，明晃晃赤裸裸的“历史分数 20”惨不兮兮的挂在那里。吓得 emptyset 赶紧打开记事本码了起来。

emptyset 想着自己退役了也没给洛咕有什么贡献，于是就打算写一篇通（垃）俗（圾）易（难）懂（读）的题解。

思路

PART I

假如我们在研究这样一类问题：以原点为圆心，以 $\sqrt N$ 为半径的圆上有多少个整点。

我们转化下，其实就是：有多少个整数对 $(a,b)$ 满足 $a^2+b^2=N$。

然而，研究二元关系总是不方便的，我们可以将二维平面看做全体复数。

如果你没学过复数，可以先这样理解，平面直角坐标系上的点 $(a,b)$ 对应复数 $a+bi$，其中 $i$ 是虚数单位，满足 $i^2=-1$。

特别的，如果虚数 $a+bi$ 中 $a,b$ 均为整数，我们又称其为高斯整数。

注意到 $a^2+b^2=N$ 等价于 $(a+bi)(a-bi)=N$，因此，问题又可以转化为：有多少个高斯整数 $z$ 满足其本身与其共轭复数 $\overline{z}$ 的乘积是 $N$。

$z=a+bi$ 的共轭复数 $\overline{z}=a-bi$。

---

PART II

既然谈到了高斯整数相乘为 $N$，我们应该康康一个数 $N$ 如何在高斯整数上分解。

我们都知道，一个数 $N$ 在整数范围内有唯一分解式，即表达为若干个因子的乘积，而其中每个因子都不能再分，这些因子也就是我们说的素数。

当然，你给其中一个因子乘以 $-1$，给另一个因子也乘以 $-1$（$-1\times -1=1$），这样的分解式依然成立。

在高斯整数范围内，一个整数 $N$ 也可以表达为若干个复数因子的乘积，而其中每个因子在高斯整数上不能再分，这些因子也就是高斯素数。

e.g. 整数 $5=(2+i)(2-i)$，而 $2+i$ 等就不能再分了，也就是说 $2+i$ 这样的就是高斯素数。

当然，这一回，你不但可以给其中一个因子乘以 $-1$，给另一个因子乘以 $-1$，你还可以给其中一个乘以 $i$，另一个乘以 $-i$（$i\times -i=1$），这样分解式依然成立。

e.g. $5=(2+i)(2-i)$

$=(-2-i)(-2+i)$ //注：一个因子乘以$-1$，另一个因子乘以$-1$

$=(2i-1)(-2i-1)$ //注：一个因子乘以 $i$，另一个因子乘以$-i$

所以，想要一个数在高斯整数上分解，我们考虑先将 $N$ 分解为若干个素数的乘积，再将其中的非高斯素数进一步分解。

---

PART III

那么我怎么知道一个素数是不是高斯素数呢？

我们可以借助费马平方和定理。

费马平方和定理：奇素数 $p$ 可以表示为两个正整数的平方和，当且仅当 $p$ 是 $4k+1$ 型的。并且在不考虑两个正整数顺序的情况下，这个表示方法唯一。

证明留作习题，读者自证亦不难有点难，当然，其实是有相当初等的证法的。

通过该定理我们得知，

$4k+3$ 型的素数是高斯素数，因此，以 $\sqrt3,\sqrt7,\sqrt{11}\cdots$为半径的圆上没有整点；

$4k+1$ 型的素数可以恰好被分解成一对共轭复数的乘积，因此，以$\sqrt5,\sqrt{13},\sqrt{17}\cdots$为半径的圆上有整点（实际上观察可知恰好是 $8$ 个整点，原因后文再讲）；

而剩下一个素数 $2$ 则比较特殊，她的确可以分解成一对共轭复数 $(1+i)(1-i)$，有趣的是这两个复数除了共轭，他们的夹角还恰好为 $90\degree$。

---

PART IV

如果用 $p$ 表示 $4k+1$ 型素数，$q$ 表示 $4k+3$ 素数（即高斯素数），那么我们可以将 $N$ 表示为这样的形式：

$$\large N=2^n\prod_{q_i=4k+3}q_i^{m_i}\prod_{p_j=4k+1}p_j^{k_j} $$

其中，每一个 $p_i$ 是可以分解为一对共轭复数的。

现在我们的目的是求将 $N$ 表示为一对共轭复数的乘积有多少种方法，那么分别讨论每一种素数：

• $4k+1$ 型素数 $p_j$ 的贡献

对于每一个 $p_j$，可以分解成 $z_j$ 和 $\overline{z_j}$，

我们可以将 $z_j$ 分配给 $N$ 的第一个因子，将 $\overline{z_j}$ 分配给 $N$ 的第二个因子（这样才能保证 $N$ 的两个因子是共轭的），

也可以将 $\overline{z_j}$ 分配给第一个因子，将 $z_j$ 分配给第二个因子。

也就是说，每一个 $p_j$ 可以有 $2$ 种分配方式。

更进一步的，对于 $p_j^{k_j}$，我们可以给第一个因子分配 $0$ 个 $z_j$、$1$ 个 $z_j\cdots$一直到 $k_j$ 个 $z_j$。

也就是说，每一个 $p_j^{k_j}$ 可以有 $k_j+1$ 种分配方式。

• $4k+3$ 型素数即高斯素数 $q_i$ 的贡献

在此之前，相信大家都知道如果一个复数没有虚部，那么该复数的共轭复数就是他本身，因为若 $z=a+0i$，$\overline z=a-0i=z$。

对于 $q_i^{m_i}$，我们想要把他分成共轭的两个因子的乘积，有多少种方案呢？

显然，如果 $2\mid m_i$，那么我们给每个因子分配 $m_i/2$ 个 $q_i$，两个因子相等，自然也就共轭了，分配方案数为 $1$。

如果 $2\nmid m_i$，哦，完蛋，因为你怎么分也不能把 $q_i^{m_i}$ 分成一对共轭复数的乘积，方案数为 $0$。

也就是说，$m_i$ 是偶数没什么影响，只要有一个 $m_i$ 是奇数，那么方案数立即归零，这个圆上没有整点。

• 素数 $2$ 的贡献

在讨论 $2$ 的问题前，请先注意一个问题：

正如前文所说，对于将 $N$ 表示为 $z\cdot\overline{z}$ 的每一种方案，$N$ 还可以表示为 $-z\cdot-\overline{z}$、$iz\cdot -i\overline{z}$、$-iz\cdot i\overline{z}$。

也就是说，最终的方案数是要乘以 $4$ 的。

对应到几何关系上，等于说每得到一个圆上的整点，还可以将它绕原点旋转 $90\degree,180\degree,270\degree$，转完的点还是在圆上的，这是乘以 $4$ 的等价解释。

现在再来看，我们说过，每一个 $2$ 虽然可以表示为 $(1+i)(1-i)$，看似提供了 $2$ 种分配方案（前者给第一个因子 或 前者给第二个因子 这两种），但是由于 $(1+i)$ 与 $(1-i)$ 的夹角是 $90\degree$，如果考虑 $2$ 的贡献会与之后的 “乘以 $4$” 计重，所以不应该考虑 $2$ 的贡献。

举个例子，半径为 $\sqrt5$ 的圆上有多少个整点，半径为 $\sqrt{10},\sqrt{20},\sqrt{40}$ 的圆上就有多少个整点。

也就是说，因为最终方案数要乘以 $4$，所以 $2^n$ 不应该产生任何影响。

---

PART V

好了，现在我们可以看这道题了，在本题中，$N=r^2$，$r$ 是给定的。

假设分解 $r$ 得到

$$r=2^n\prod_{q_i=4k+3}q_i^{m_i}\prod_{p_j=4k+1}p_j^{k_j} $$

那么

$$N=2^{2n}\prod_{q_i=4k+3}q_i^{2m_i}\prod_{p_j=4k+1}p_j^{2k_j} $$

我们很高兴的看到，$N$ 的每一个高斯素数因子 $q_i$ 的指数 $2m_i$ 都是偶数，不用担心归零了，他们不会产生任何影响。

更进一步的，方案数只与 $2k_j$ 有关。

上文提到，每一个 $p_j^{k_j}$ 可以有 $k_j+1$ 种分配方式，那么每一个 $p_j^{2k_j}$ 可以有 $2k_j+1$ 种分配方式。

再考虑上乘以 $4$，得到圆上的整点数为

$$4\prod_{p_j=4k+1}(2k_j+1)$$

复杂度为分解素因数 $\Theta(\sqrt r)$。

代码

#include <cstdio>
int r;
long long ans = 1;
int main() {
	scanf("%d", &r);
	for(int i = 2, cnt; i*i <= r; ++i)
		if(!(r % i)) {
			cnt = 0;
			do r /= i, ++cnt; while(!(r % i));
			if(i%4 == 1) ans *= cnt<<1|1;
		}
	if(r != 1 and r%4 == 1) ans *= 3;
	printf("%lld\n", ans<<2);
}

p.s

好了好了这可能是最后一次在洛咕灌水了，算是最后一件与 OI 有关的事情吧，溜了溜了。