1. 问题引入从一道经典数论题说起最近在整理数论相关的算法模板时又翻到了洛谷上那道经典的 P2508 题——“圆上的整点”。这道题初看描述很简单给定一个以原点为圆心、半径为r的圆求圆周上横纵坐标均为整数的点有多少个。换句话说就是求方程x^2 y^2 r^2的整数解(x, y)的组数。很多刚接触数论的同学可能会想这不就是枚举吗从-r到r遍历x然后检查y sqrt(r^2 - x^2)是不是整数不就行了对于小范围的r这确实可行。但题目给出的r范围可以非常大比如r 2e9直接枚举的复杂度是O(r)显然会超时。这就迫使我们必须去寻找一个更高效的数学方法。这道题真正的价值在于它完美地串联起了初等数论中的多个核心概念勾股数、素数分解、二次剩余并最终指向了一个更强大的工具——高斯整数。高斯整数将复数引入数论为解决这类与平方和相关的丢番图方程提供了系统性的框架。而题目中提到的“高斯素数模板”正是实现这个框架的代码核心。今天我就结合自己多次实现和调试的经验把这个问题的来龙去脉、背后的数学原理以及一个鲁棒性强的代码模板完整地梳理一遍。无论你是正在备赛的 OIer还是对数论感兴趣的开发者相信这篇内容都能帮你彻底吃透这个问题。2. 核心思路拆解从勾股数到高斯整数要高效解决x^2 y^2 r^2我们首先得跳出“圆”的几何直观从代数角度重新审视它。方程两边同时除以r^2并没有帮助关键的一步是对方程右边的r^2进行质因数分解。但这里有个更本质的视角我们求解的其实是所有满足a^2 b^2 n其中n r^2的整数对(a, b)。这个问题在数论中历史悠久其解的数量与n的质因数分解形式有着深刻的联系。2.1 费马平方和定理与模4余1的素数一个关键的突破口是费马平方和定理。这个定理告诉我们一个奇素数p可以表示为两个整数的平方和即p a^2 b^2的充要条件是p ≡ 1 (mod 4)。例如51^22^2132^23^2。而模4余3的素数如3, 7, 11永远不能表示为两个整数的平方和。这个定理为我们指明了方向方程x^2 y^2 n的解很大程度上取决于n的质因数中那些模4余1的素数是如何“贡献”的。对于一个素数p ≡ 1 (mod 4)它可以被唯一地分解为两个共轭复数的乘积p (a bi)(a - bi)其中a, b是正整数。这里的abi和a-bi就是高斯整数。2.2 引入高斯整数将问题升维什么是高斯整数简单说就是实部和虚部都是整数的复数形式为a bi其中a, b ∈ Zi是虚数单位。所有高斯整数构成一个整环记作Z[i]。在这个环里我们也可以定义“素数”即高斯素数。普通整数中的素数在高斯整数环里不一定还是素数。普通素数p ≡ 3 (mod 4)在高斯整数环中仍然是素数不可约。例如3、7、11。普通素数p ≡ 1 (mod 4)在高斯整数环中可以分解为两个共轭高斯素数的乘积即p (abi)(a-bi)。例如5 (2i)(2-i)。素数p 2这是一个特例2 (1i)(1-i)并且(1i)和(1-i)是相伴元相差一个单位因子i或-1等。单位因子是指模长为1的高斯整数1, -1, i, -i。它们在高斯整数中的作用类似于整数中的±1。现在关键的一步来了方程x^2 y^2 n可以改写为(x yi)(x - yi) n。我们把xyi和x-yi看作高斯整数。于是求解整数对(x, y)的问题就转化为了在高斯整数环Z[i]中寻找所有满足α * \bar{α} n的高斯整数α的问题其中\bar{α}是α的共轭。由于n是普通整数我们可以先对n在整数范围内进行质因数分解然后研究每个质因子在高斯整数环中如何进一步分解最后组合出所有可能的α。2.3 算法流程总览基于以上理论求解x^2 y^2 r^2的整数解个数的算法流程可以概括如下计算n r^2我们最终要求的是a^2 b^2 n的解。对n进行质因数分解n 2^e * ∏ (p_i)^{k_i} * ∏ (q_j)^{l_j}。其中p_i是模4余1的素数。q_j是模4余3的素数。分析各因子对解的贡献因子2它对解的数量没有决定性影响主要影响解的“形式”我们稍后讨论。模4余3的素数q_j如果某个q_j的指数l_j是奇数那么方程a^2 b^2 n无解。因为q_j在高斯整数中不可约无法“配对”成共轭形式。如果所有l_j都是偶数则每个q_j^{l_j}可以写成(q_j^{l_j/2})^2它只影响最终α的范数模长不影响解的组合方式数量。模4余1的素数p_i这是解的来源。设p_i (a_i b_i i)(a_i - b_i i)。那么因子p_i^{k_i}在高斯整数环中的分解会产生多种选择。具体来说对于幂次k_i我们在分配因子给α时对于每个p_i因子可以选择分配(a_ib_i i)^t * (a_i - b_i i)^{k_i - t}给α其中t可以从0取到k_i。但由于α和\bar{α}共轭不同的t可能对应相同或对称的解。组合计数与去重综合所有p_i因子的选择并考虑单位因子 (1, -1, i, -i) 和交换x, y、正负号带来的对称解最终可以推导出解的总数公式。这个推导过程稍显复杂但结论非常优美。对于方程x^2 y^2 n设n的质因数分解中所有模4余1的素因子的指数分别为k1, k2, ...那么正整数解(x, y)即x0, y0的个数为N_pos ( (k11)(k21)... ) / 2如果这个乘积是奇数否则为( (k11)(k21)... ) / 2。实际上更常用的公式是直接计算所有整数解包括正负和零的数量。3. 解的数量公式推导与最终结论我们跳过繁琐的中间推导直接给出针对原问题x^2 y^2 r^2的最终结论性公式。令n r^2。对n进行质因数分解。如果n的质因数中存在任何一个模4余3的素数且其次数为奇数则方程无解。因为r^2的每个质因子次数必然是偶数所以这一条件在本题中自动满足n是完全平方数我们可以忽略。但理解这一点对一般情况很重要。重点考察模4余1的素数因子。设n的分解中模4余1的素因子p_i的指数为c_i。那么方程x^2 y^2 n的整数解(x, y)的总数包括(x, y), (-x, y), (x, -y), (-x, -y)以及坐标轴上的点为N_total 4 * ∏ (c_i 1)公式解释因子4来自于(±x, ±y)的符号组合。注意当x或y为0时会产生重复计数但公式仍然成立因为它计算的是所有有序整数对。乘积项∏ (c_i 1)来自于每个模4余1的素因子p_i^{c_i}。在高斯整数分解中这个因子可以产生(c_i 1)种本质上不同的分配方式给α即xyi。对于模4余3的素因子由于其指数在n r^2中必为偶数设为2d它整体以(q_j^d)^2的形式出现不提供额外的组合选择因此不影响乘积项。对于素因子2它也不影响这个乘积项。回到原题题目要求的是圆x^2 y^2 r^2上的整点。我们直接令n r^2对r进行质因数分解那么n的分解就是r的分解中每个指数乘以2。因此算法步骤可以优化为直接对r分解对r进行质因数分解。如果r的质因数中存在任何一个模4余3的素数且其次数为奇数则该项对最终解的个数贡献乘数因子为1即不增加解的种类。实际上在公式中我们只关心模4余1的素数。设r的分解中模4余1的素因子p_i的指数为e_i。那么n r^2中对应p_i的指数c_i 2 * e_i。代入公式N_total 4 * ∏ (2 * e_i 1)这就是本题的最终计算公式。整个算法的核心就变成了对r质因数分解找出所有模4余1的质因子及其指数然后计算4 * ∏ (2*e_i 1)。注意这个公式计算的是所有整数解包括(r,0), (0,r), (-r,0), (0,-r)以及x或y为0的其他点如果r本身是某个勾股数的倍数。题目通常要求的就是这个总数。4. 算法实现与“高斯素数模板”解析理论很优美但实现起来有几个需要注意的坑。下面我给出一个鲁棒的C实现并逐行解析其作为“模板”的要点。#include iostream #include cmath using namespace std; typedef long long ll; // 计算圆 x^2 y^2 r^2 上的整点个数 ll count_lattice_points_on_circle(ll r) { if (r 0) return 1; // 只有原点(0,0)一个点 ll n r; ll ans 1; // 初始化为1用于连乘 // 处理因子2它对公式的乘积项没有贡献但先把它从n中除去方便后续只处理奇素数 while (n % 2 0) { n / 2; } // 分解奇素数因子 for (ll i 3; i * i n; i 2) { if (n % i 0) { int cnt 0; while (n % i 0) { n / i; cnt; } // 核心判断如果素数模4余1则根据公式贡献 (2*cnt 1) 倍 if (i % 4 1) { ans * (2 * cnt 1); } // 如果素数模4余3且cnt为奇数理论上无解但这里是r^2cnt自动加倍后为偶数所以忽略。 // 实际上对于模4余3的素数无论cnt为何值都不参与乘积。 } } // 处理可能剩余的大于sqrt(n)的质因子 if (n 1) { // 判断这个剩余的质因子是否模4余1 if (n % 4 1) { ans * (2 * 1 1); // 此时指数cnt为1 } // 如果模4余3同样忽略 } return ans * 4; // 最终乘以4 } int main() { ll r; cin r; cout count_lattice_points_on_circle(r) endl; return 0; }4.1 模板代码关键点解析r 0的特殊情况当半径为0时圆退化为一个点(0,0)。这是一个边界情况需要单独处理返回1。因子2的处理在质因数分解循环开始前先用一个while循环去掉所有因子2。这是因为根据公式因子2不参与最终的乘积计算∏ (2*e_i 1)。提前去掉偶数因子可以使后续的循环i 2只遍历奇数提高效率。数学上2 (1i)(1-i)但它的存在不影响模4余1素因子带来的组合数。核心循环与判断for (ll i 3; i * i n; i 2)这是标准的试除法质因数分解只检查奇数。内层while循环统计当前质因子i的指数cnt。if (i % 4 1)这是算法的灵魂。只有模4余1的质因子才对答案有贡献。贡献的乘数因子是(2 * cnt 1)。这里的cnt是r中该质因子的指数e_i所以2*cnt就是r^2中的指数c_ic_i 1即(2*cnt 1)。对于i % 4 3的质因子我们直接忽略。因为r^2中它的指数是2*cnt为偶数在高斯整数分解中它只是一个实部为q_j^{cnt}、虚部为0的高斯整数或其倍数不产生新的组合。如果cnt是奇数在r中那么r^2中该因子指数2*cnt仍是偶数所以不影响。如果是在求解一般的x^2y^2nn非完全平方数时就需要检查cnt的奇偶性来判断是否有解。处理剩余的大质因子试除法结束后如果n 1说明n本身就是一个大于原sqrt(n)的质因子。需要对这个质因子进行同样的模4判断。最终返回return ans * 4;对应公式中的因子4计算所有象限和符号的解。4.2 模板的通用性与“高斯素数”部分这个模板之所以被称为“高斯素数模板”是因为其核心逻辑完全基于高斯整数的理论判断i % 4 1这正是在识别那些在高斯整数环中可分解的普通素数即非高斯素数的普通素数。乘数因子(2*cnt1)这来源于高斯整数Z[i]中对理想(p)^{c_i}进行分解时其范数为p^{c_i}的元素个数的计数。c_i 1本质上是幂次c_i的分配方案数。因此这个模板可以稍作修改用于解决更一般的问题例如求x^2 y^2 n的整数解个数需增加对模4余3素数指数奇偶性的判断。求所有解的具体值需要回溯构造高斯整数α更为复杂。5. 复杂度分析与优化上述模板使用试除法分解质因数时间复杂度为O(√n)其中n是初始的r。对于r 2e9√r大约为44721在极限数据下单次计算是可行的。但如果有多组测试数据或者r更大就需要优化。5.1 预处理素数表最常用的优化是先用埃氏筛或欧拉筛预处理出√(max_r)范围内的所有素数存放在一个数组中。在分解r时只用这些素数去试除。vectorint primes; void sieve(int limit) { vectorbool is_prime(limit 1, true); is_prime[0] is_prime[1] false; for (int i 2; i limit; i) { if (is_prime[i]) { primes.push_back(i); for (int j i * i; j limit; j i) { is_prime[j] false; } } } } ll count_lattice_points_optimized(ll r, const vectorint primes) { if (r 0) return 1; ll n r; ll ans 1; while (n % 2 0) n / 2; for (int p : primes) { if ((ll)p * p n) break; // 素数平方超过当前n终止 if (n % p 0) { int cnt 0; while (n % p 0) { n / p; cnt; } if (p % 4 1) { ans * (2 * cnt 1); } } } if (n 1) { if (n % 4 1) { ans * (2 * 1 1); } } return ans * 4; }这样分解部分的复杂度就从O(√n)降到了O(π(√n))其中π(x)是小于x的素数个数大约为x / ln(x)效率提升显著。5.2 注意大数溢出题目中r可达2e9计算过程中ans可能超过int范围。因此务必使用long long(ll)。在连乘ans * (2 * cnt 1)时尽管最终答案可能在int内但中间过程可能溢出。用ll是安全的。5.3 一个常见的计算错误有人可能会错误地先计算r^2再对r^2进行质因数分解。这不仅是低效的数值变大而且在r很大时r^2会超出long long的范围2e9的平方是4e18接近long long上限9e18有溢出风险。我们直接对r分解利用公式中指数乘2的关系是更优且安全的选择。6. 实例演练与调试我们通过几个例子来验证算法和代码。例1r 5r 5质因数分解5(模4余1指数1)。公式计算ans 4 * (2*1 1) 4 * 3 12。实际解(±5,0), (0,±5), (±3,±4), (±4,±3)。共12个点。验证正确。例2r 25 (5^2)r 5^2质因数分解5(模4余1指数2)。公式计算ans 4 * (2*2 1) 4 * 5 20。实际解除了(±25,0), (0,±25), (±15,±20), (±20,±15)还有(±7,±24), (±24,±7)。因为25^2 625 7^224^2 15^220^2。共20个点。例3r 10r 2 * 5。分解去掉因子2后n5。质因子5(模4余1指数1)。公式计算ans 4 * (2*1 1) 12。实际解x^2y^2100的解(±10,0), (0,±10), (±6,±8), (±8,±6)。共12个点。例4r 3r 3(模4余3的素数)。分解3不是模4余1的素数因此乘积项为∏ (2*e_i1)为空积等于1。公式计算ans 4 * 1 4。实际解x^2y^29的解只有(±3,0), (0,±3)。共4个点。验证正确。在调试时可以先用暴力枚举小数据验证算法的正确性确保对边界情况如r0,r1的处理无误。7. 从模板到理解掌握其思想精髓“高斯素数模板”的价值不仅仅在于解决这道题。它提供了一个经典的范例展示了如何将数论问题转化为代数问题整数环 - 高斯整数环利用更丰富的代数结构来简化计数。这种思想在解决其他问题时也很有用比如四平方和定理任何正整数都可表示为四个整数的平方和。其证明也涉及四元数等代数结构。佩尔方程x^2 - D*y^2 1可以通过连分数或代数数域的理论求解。计算勾股数的个数给定斜边c求有多少对正整数(a,b)满足a^2b^2c^2且ab。这本质上就是求c^2的约数中模4余1的因子个数等问题与本文方法同源。理解了这个模板背后的高斯整数理论你就掌握了一把打开数论中平方和问题大门的钥匙。下次遇到类似问题不妨先想想能不能把方程改写为复数的乘积能不能在更大的整数环里考虑因式分解