发布日期: 2022-09-16

更新日期: 2024-04-30

文章字数: 2k

洛谷P2508 [HAOI2008]圆上的整点题解

题目链接：P2508 [HAOI2008]圆上的整点

题意：

求一个给定的圆 $(x^2+y^2=r^2)$ ，在圆周上有多少个点的坐标是整数。

输入格式：

一个正整数 $r$ 。

输出格式：

整点个数。

数据范围：

$1\le r\leq 2\times 10^9$

关键词：高斯素数、复平面、费马平方和定理、乘法原理

圆心为原点，半径为 $r$ 的圆周上有多少个整点？

实际上我们可以把这个问题转化为以下的形式

存在多少个整数对 $(a,b)$ 满足 $a^2 + b^2 = N$ ，其中 $N \in \mathbb{Z}^+$ 。

对于这样的二元问题，我们可以将二维平面看作复平面。

首先我们要知道这么几个前置知识。

1.高斯整数：

高斯整数是实部和虚部都为整数的复数。（只要知道这个就行了）

所有的高斯整数组成了一个整环，写作 $\mathbb{Z}[i]$ 。

$\mathbb{Z}[i] = \{a+bi \mid a,b \in \mathbb{Z}\}$

高斯整数组成了一个唯一分解整环，其可逆元为 $1,-1,i,-i$ 。

2.高斯素数：

$\mathbb{Z}[i]$ 的素元素又称为高斯整数。

高斯整数 $a+bi$ 是素数当且仅当以下两命题之一成立。

$a,b$ 中有一个为零，并且另一个是形如 $4k+3$ 的素数（或其相反数 $-(4k+3)$ ）
$a,b$ 均不为零，而 $a^2 + b^2$ 是素数。

3.费马平方和定理：

奇素数能被表示为两个平方数之和的充分必要条件是该素数被 $4$ 除余 $1$ 。

换个说法，奇素数 $p$ 可以表示为两个正整数的平方和，当且仅当 $p$ 是 $4k+1$ 型的。

并且在不考虑两个正整数顺序的情况下，这个表示方法唯一。

~~再换个说法，~~

$\forall p \in \mathbb{P} \land p =4n+1~(n\in \mathbb{Z}^+),~\exists a,b\in\mathbb{Z^+} \ \ \textrm{s.t.}\ \ p =a^2 + b^2$

注意，这里是 $4k+1$ 型，刚刚的费马素数是 $4k+3$ 型。

~~前置知识好像有亿点多~~

回到刚刚的问题，存在多少个整数对 $(a,b)$ 满足 $a^2 + b^2 = N$

因为我们把二维平面看作了复平面，所以 $a,b$ 分别对应实部和虚部，且 $a,b$ 为整数。

而显然有

$a^2 + b^2 = N \Rightarrow (a+bi)(a-bi) = N$

因此题目又转化为了：有多少个高斯整数 $z$ 满足其本身与其共轭复数 $\overline{z}$ 的乘积是 $N$ 。

不难发现高斯整数的共轭复数也是高斯整数。

考虑一个正整数 $N$ 在 $\mathbb{Z}[i]$ 上的分解。

梦回集训。当时 AprilGrimoire 跟我们讲唯一分解整环，没有一个听懂的。

首先，$N$ 在 $\mathbb{Z}^+$ 上存在唯一分解（根据算术基本定理）

也就是任意一个 $N$ 都可以表示成以下的形式

$N = p_1^{k_1} p_2^{k_2} \cdots p_t^{k_t}\quad(p \in \mathbb{P})$

如果我们给其中某对 $p_x,p_y$ 分别乘上 $i,-i$ ，看看会怎么样

$\begin{aligned} &\quad p_1^{k_1} p_2^{k_2} \cdots p_x^{k_x-1}p_y^{k_y-1}\cdots p_t^{k_t}\cdot ip_x\cdot (-i)p_y \\&=p_1^{k_1} p_2^{k_2} \cdots p_x^{k_x}p_y^{k_y}\cdots p_t^{k_t} \\&=N \end{aligned}$

因此 $N$ 在 $\mathbb{Z}[i]$ 上的分解，可以先将 $N$ 在 $\mathbb{Z}^+$ 上分解为若干个素数的乘积，然后将非高斯素数再进一步分解。

根据费马平方和定理以及刚才的推导可知

$4k+1$ 型的素数可以被恰好分解成一堆共轭复数的乘积。
$4k+3$ 型的素数是高斯素数。
$2$ 比较特殊，它的确可以被分解为 $(1+i)(1-i)$ ，但是我们单独考虑它。

记 $p$ 为 $4k+1$ 型素数（ $p=5,13,16,\cdots$ ），$q$ 为 $4k+3$ 型素数（ $q=3,7,11,\cdots$ ）（也是高斯素数），则

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

显然每个 $p_i$ 都是可以被分解为一对共轭复数的。

现在我们的目的是求将 $N$ 表示为若干对共轭复数的乘积有多少种方法。

首先考虑 $p_i$ 的贡献。

对于每个 $p_i$ ，我们可以把它分解为 $z_i$ 和 $\overline{z_i}$

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

当然反过来非配也是可以的。因此对于每个 $p_i$ 可以有 $2$ 种分配方式。

进一步的， $p_i^{k_i}$ 可以有 $k_i+1$ 种分配方式，因为我们可以给第一个因子分配 $0,1,\cdots,k_i$ 个 $z_i$ 。

然后考虑 $q_i$ 的贡献。

也就是要计算把 $q_i^{m_i}$ 分成共轭的两个因子的乘积的方案数。

显然，如果 $2 \mid m_i$ ，则给每个因子分配 $\frac{m_i}{2}$ 个 $q_i$

此时两个因子相等且虚部为 $0$ ，但是也是共轭的。方案数为 $1$

如果 $2 \not\mid m_i$ ，方案数为 $0$ 。因此只要存在一个 $m_i$ 为奇数，答案一定为 $0$ 。

最后考虑 $2$ 的贡献。

首先有一个问题

高斯整数组成了一个唯一分解整环，其可逆元为 $1,-1,i,-i$ 。

对于刚刚 $z_i \times \overline{z_i}$ 的分解，实际上可以分解成以下四种情况

$z_i \times \overline{z_i} \quad (-z_i) \times (-\overline{z_i}) \quad -iz_i \times i\overline{z_i} \quad iz_i \times (-i)\overline{z_i}$

对应到复平面上，就是旋转了 $0,~\frac{\pi}{2},~\pi,~\frac{3\pi}{2}$ 。因此答案数实际上是要乘以 $4$ 的。

根据复数乘法的几何意义，两个复数相乘就是辐角相加模相乘。

是的，我又打算整一个复数的总结。然后就咕咕咕了。

而对于 $(1+i),(1-i)$ ，可以发现

$(1+i) \times (-i) = (1-i) \\(1-i) \times i = (1+i)$

因此在给每个因子分配不同个数的 $(1+i),(1-i)$ 的过程，其实相当于让他们乘上了 $i$ 或 $-i$ 。

这与我们刚刚的计数会有冲突（给第一个因子乘上 $1,-1,i,-i$ ，并让第二个乘以对应的共轭复数），因此实际上我们不需要统计 $2$ 交换产生的贡献。

那么 $2^n$ 呢？其实根据归纳法可知，无论乘若干次都会与刚刚的计数冲突。

因此综上，我们不需要考虑 $2^n$ 的贡献。

写了几个小时了，总算可以考虑原题了。

由于 $N=r^2$ ，因此有

$r = 2^n \prod_{p_i = 4k+1}p_i^{k_i}\prod_{q_i = 4k+3} q_i^{m_i}$ $N = 2^{2n} \prod_{p_i = 4k+1}p_i^{2k_i}\prod_{q_i = 4k+3} q_i^{2m_i}$

因此我们不需要考虑 $q_i$ 导致方案数为 $0$ 的情况了。（见 $q_i$ 贡献的分析）

故我们只需要考虑 $p_i$ 的贡献。

根据上面的分析，答案为（ $2k_i+1$ 是因为 $k_i$ 变成 $2k_i$ 了）

$4 \times \prod_{p_i = 4k+1} (2k_i + 1)$

因此我们只需要分解一下质因数就好了。

时间复杂度 $\mathcal{O}(\sqrt{n})$

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)())

int r,ans=1;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> r;
    for(int i=2,cnt; i <= r/i; i++)
        if(r % i == 0)
        {
            cnt=0;
            do { r/=i; ++cnt; } while(r % i == 0);
            if(i % 4 == 1) ans *= cnt * 2 + 1;
        }
    if(r != 1 && r % 4 == 1) ans *= 3;
    cout << ans * 4 << '\n';
    return 0;
}