发布日期: 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;
}