圆上的整点
题目链接：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\)。
- \(4k+3\) 是高斯质数，那就对应的圆上没有整点。
- \(4k+1\) 是恰好可以被分成一对共轭负数的乘积，那就对应的圆上有整点（至于有多少个我们后面再看）
- \(2\) 是可以分成 \((1+i)(1-i)\)，而且特殊的是这两个成 \(90°\)（为啥特殊后面会用到）
然后考虑一个数质因数分解之后要怎么弄，我们考虑把三种质数分开来：
\(N=2^p\prod\limits_{a_i=4k+3}a_i^{m_i}\prod\limits_{b_i=4k+1}b_i^{n_i}\)
其中 \(2,b_i\) 是可以分解的，那问题是我们要把 \(N\) 分成一对共轭质数。
我们思考有怎样的分配方式，一种是能分解成共轭的，一边一个，要么是两个一样的，一遍给一个（因为同乘也是可以的，相当于把圆放大罢了，对于的位置还是在整点）
对于每个分类讨论：
- \(4k+1\)
我们可以把它分解两种高斯质数，那如果是 \(n_i\) 个这样的，那我们可以选择给左边 \(0\sim n_i\) 个，所以方案是 \(n_i+1\)。 - \(4k+2\)
这种不能拆，就只能给两边，所以如果 \(m_i\) 是奇数就不行整个答案是 \(0\)，否则就不变。 - \(2\)
那看起来也是跟 \(4k+1\) 一样？
然后发现我们漏了一个问题，你上面这个拆只是在正整数的位置，你总的位置还有四个呢！
那答案就要乘上 \(4\)，如果在二维平面上形象地表示一下的话，就是每次转 \(90\) 度的感觉。
但是这个时候 \(2\) 就有问题了，你这样搞就会重复，具体来讲只有四个不一样的，所以你可以相当于 \(2\) 不用管，最后答案乘 \(4\) 即可。
然后注意到题目是 \(x^2+y^2=r^2\)。
所以 \(N=r^2\)，当然直接单纯的这样是不行的。
考虑看看式子：
\(r=2^p\prod\limits_{a_i=4k+3}a_i^{m_i}\prod\limits_{b_i=4k+1}b_i^{n_i}\)
\(N=2^r=2^{2p}\prod\limits_{a_i=4k+3}a_i^{2m_i}\prod\limits_{b_i=4k+1}b_i^{2n_i}\)
改一改就好了。
代码
#include<cstdio>
#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;
}