$题目描述$

在平面直角坐标系上，以原点为圆心做半径为 $r$ 的圆，问圆上有多少个整点。

$前置知识$

$高斯整数$

到一个复数 $(a+bi)$ 满足 $a\in Z,b\in Z$ 时，$(a+bi)$ 就是一个高斯素数。

$高斯素数$

若一个高斯整数可以分解成多个高斯整数的乘积，则它就不是高斯素数。

例如 $5=(2+i)(2-i)$，所以它不是高斯素数，但是 $2+i$ 和 $2-i$ 都是高斯素数，因为它们不能再分解。

$分析$

设有整点 $(a,b)$，满足 $a^2+b^2=r^2$。

将其转为复平面，则有 $(a+bi)(a-bi)=r^2$。

首先引入费马平方和定理，一个素数可以分解成两个数的平方，当且仅当它可以表示为 $4k+1(k\in Z_+)$ 的形式，证明不会。

则所有素数都可以分成三类：$4k+1$ 型，$4k+3$ 型，$2$ 型。

若将 $r$ 分解质因数，则得到

$$r = 2^t \prod_{p_j = 4k + 1} p_j^{c_j} \prod_{p_j = 4k+3} p_j^{c_j}$$

$$r^2 = 2^{2t} \prod_{p_j = 4k + 1} p_j^{2c_j} \prod_{p_j = 4k+3} p_j^{2c_j} $$

分为三类分别计算贡献。

4k+1 型

$p_j = 4k + 1$，则 $p$ 可以分解为两个共轭高斯素数，两边各一个，答案乘以 $2c_j + 1$。

4k+3 型

由于不可能分解，所以只能单独放，由于它的次幂为偶数，所以刚好可以使两边平衡，无贡献。

2 型

由于 $2 = (1+i)(1-i)$，本来贡献为 $2$，但是 $(1+i)$ 和 $(1-i)$ 夹角为 $90$ 度，所以有重复，故不算贡献

综上所述，最终答案为

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

时间复杂度 $O(\sqrt{r})$。

$代码$

#include <bits/stdc++.h>
using namespace std;

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

$参考资料$

video