P2508 [HAOI2008]圆上的整点

P2508 [HAOI2008]圆上的整点

题解

题目大意

给定$r$, 求$x^2 + y^2 = r^2$ 的整数解的个数, 其中$r \le 2000000000$。

解法

题目其实就是在求以原点为圆心，以$r$为半径的圆上有多少个整点。

首先我们可以先将二维平面看做全体复数，满足题目中的式子的解其实就是满足，$(a + bi)(a - bi) = r^2$的解的个数。

然后说明一个数学定义， 如果虚数$a + bi$ 中$a, b$均为整数， 则称这个虚数为高斯整数，

现在问题又进一步转化为， 有多少个高斯整数$z$满足其本身与其共轭复数$\bar{z}$的乘积为$r ^ 2$。

现在需要讨论的是一个整数如何分解成高斯整数。

首先对于每一个整数，根据算术基本定理都能将其分解成若干个素数的乘积，同样的， 一个整数$N$也可以表示为若干个复数因子的乘积，这些因子在高斯整数上能再分，也就是高斯素数。

首先我们可以先将一个整数$N$在整数上分解为若干个素数的乘积，然后再将其中的非高斯素数进一步分解。

接下来需要解决的是如何判断一个素数是不是高斯素数。

引入费马平方和定理：

奇素数$p$可以表示为两个正整数的平方和，当且仅当$p = 4 k + 1$， 并且方法唯一。

通过该定理我们可以得知，

• $4k + 3$型的素数为高斯素数，
• $4k + 1$型的素数可以被分解为一对共轭复数的乘积，
• $2$可以被分解为$(1 + i) (1 - i)$。

假设$p = 4k + 1$型素数， $q = 4k + 3$型素数，$N$就可以被表示为：

$$N = 2^n \prod _ {q_i = 4k + 3}q_i ^ {m_i} \prod _{p _j = 4 k + 1} p_j ^{k_j}$$

然后就可以接着分解$p _j$为一对共轭复数，接下来就是讨论每一种素数的贡献来统计有多少种方法。

1. $4k + 1$型素数的贡献

   对于每一个$p_j$，将其分解为$z_j$ 和$\bar{z_j}$，然后一个分在前一个因子， 一个分在后一个因子，保证共轭或者相反，有两种分配方式， 那么对于$p_j ^ {k _J}$， 就会有$k_j + 1$ 种分配方式。

2. $4k + 3$型素数的贡献

   由于高斯素数不能分为对应的乘积形式， 可以将其分解为$(a+0i)(a-0i)$，那么对于$q_i^{m_i}$，为了保证共轭，$2 \mid m_i$时贡献为$1$, 当$2 \not\mid m_i$时对应得贡献就为$0$。

3. 素数$2$的贡献

   由于$2 = (1 + i) (1 - i)$，然而$1 + i$ 和$1-i$的夹角为$90^\circ$，最后统计答案$\times 4$时计算重复，计算时其不应该产生任何贡献。

假设分解$r$得：

$$r = 2 ^ n \prod _{q_i = 4k + 3}q_i ^ {m _ i} \prod _{p _ j = 4k + 1} p_j ^ {k _j}$$

对应得$N$ 就可分解为：

$$N = 2 ^ {2n} \prod _{q_i = 4k + 3}q_i ^ {2m _ i} \prod _{p _ j = 4k + 1} p_j ^ {2k _j}$$

这样的话每一个高斯素数的因子都为偶数，都有贡献，那么最后的答案为：

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

复杂度为$O(\sqrt r)$。

#include<bits/stdc++.h>

using namespace std;

#define int long long

int r, ans = 1;

signed main()
{
    cin >> r;
    for(int i = 2; i * i <= r;  i++)
    {
        if(r % i != 0)continue;
        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 *= (1 * 2 + 1);
    cout << ans * 4;
    return 0;
}

tips: 勾股数组定理， 每个本原勾股数组$(a, b, c)$， 其中$2 \not \mid a, 2 \mid b$，都可以从以下公式得出。

$a = st, b = \frac{s^2 - t^2}{2}, c = \frac{s^2 + t^2}{2}$， 其中$s > t \ge 0$是任意没有公因数的奇数。