【luogu P2508】圆上的整点（高斯素数模板）

圆上的整点

题目链接：luogu P2508

题目大意

给你一个圆，问你圆周上有多少个点的坐标是整点。

思路

考虑一个东西叫做高斯整数。
其实它是复数，是 $a+bi$ 中 $a,b$ 都是整数的复数。

那它跟它共轭的乘积其实就是 $a^2+b^2$，所以我们可以把它转化成 $a^2+b^2=N$ 这个东西，满足条件的高斯整数个数。

---

那既然是这样我们就考虑这个 $N$ 要怎么在高斯整数上分解。
那在整数范围有唯一的分解，就是质因数分解嘛。
不过准确一点其实可以说是不唯一，因为你可以同时给两个质因数取反，得到的还是可以，毕竟负数也是整数。

那在高斯划分中，你也可以划分成一些高斯整数，它在高斯整数上不能再分，那这些就是高斯质数。
在弄 $-1$ 自然可以，你会发现你甚至可以弄 $i$（准确来讲是一个 $i$ 一个 $-i$，因为 $i(-i)=-(-1)=1$）。

---

那么就是一个问题了，怎么知道一个高斯整数是不是高斯质数。
我们可以用一个叫做费马平方和的定理。

费马平方和定理：奇素数 $p$ 可以表示乘两个数的平方和当且仅当 $p$ 是形如 $4k+1$，其中 $k$ 为整数。
不考虑两个正整数顺序的时候方法唯一。

（有人不会证，不过想看证明的可以去看百度百科，看着好像不难懂）

那我们就分类讨论一下，对于质数分成 $2,4k+1,4k+3$。

1. $4k+3$ 是高斯质数，那就对应的圆上没有整点。
2. $4k+1$ 是恰好可以被分成一对共轭负数的乘积，那就对应的圆上有整点（至于有多少个我们后面再看）
3. $2$ 是可以分成 $(1+i)(1-i)$，而且特殊的是这两个成 $90°$（为啥特殊后面会用到）

---

然后考虑一个数质因数分解之后要怎么弄，我们考虑把三种质数分开来：
$N=2^p\prod _{a_i=4k+3}{a}_i^{m_i}\prod _{b_i=4k+1}{b}_i^{n_i}$

其中 $2,b_i$ 是可以分解的，那问题是我们要把 $N$ 分成一对共轭质数。
我们思考有怎样的分配方式，一种是能分解成共轭的，一边一个，要么是两个一样的，一遍给一个（因为同乘也是可以的，相当于把圆放大罢了，对于的位置还是在整点）

对于每个分类讨论：

1. $4k+1$
   我们可以把它分解两种高斯质数，那如果是 $n_i$ 个这样的，那我们可以选择给左边 $0\sim n_i$ 个，所以方案是 $n_i+1$。
2. $4k+2$
   这种不能拆，就只能给两边，所以如果 $m_i$ 是奇数就不行整个答案是 $0$，否则就不变。
3. $2$
   那看起来也是跟 $4k+1$ 一样？

然后发现我们漏了一个问题，你上面这个拆只是在正整数的位置，你总的位置还有四个呢！
那答案就要乘上 $4$，如果在二维平面上形象地表示一下的话，就是每次转 $90$ 度的感觉。
但是这个时候 $2$ 就有问题了，你这样搞就会重复，具体来讲只有四个不一样的，所以你可以相当于 $2$ 不用管，最后答案乘 $4$ 即可。

---

然后注意到题目是 $x^2+y^2=r^2$。
所以 $N=r^2$，当然直接单纯的这样是不行的。
考虑看看式子：
$r=2^p\prod _{a_i=4k+3}{a}_i^{m_i}\prod _{b_i=4k+1}{b}_i^{n_i}$
$N=2^r=2^{2p}\prod _{a_i=4k+3}{a}_i^{2m_i}\prod _{b_i=4k+1}{b}_i^{2n_i}$
改一改就好了。

代码

#include
#define ll long long

using namespace std;

int n;
ll ans;

void slove(int x, int num) {
	if (x == 2) {
		return ;
	}
	if (x % 4 == 3) {
		if ((2 * num) & 1) ans = 0; return ;
	}
	if (x % 4 == 1) {
		ans *= (2 * num + 1); return ;
	}
}

int main() {
	scanf("%d", &n); ans = 1;
	for (int i = 2; i * i <= n; i++) {
		if (n % i != 0) continue;
		int num = 0; while (n % i == 0) n /= i, num++;
		slove(i, num);
	}
	if (n > 1) slove(n, 1);
	
	printf("%lld", ans * 4);
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33