企业官网建设流程全解析

“整点计数”这四个字，放在数论题里总会让人产生一种“这是几何题”的错觉。我第一次看到这道题时，题面只有一句话：给定 $N$，求所有满足 $x^2+y^2\le N$ 的有序整数对 $(x,y)$ 的数量，答案对一个大质数取模。题目标签里清清楚楚写着“min_25筛”。我当时的第一反应是：圆内整点问题不是枚举横坐标就能 $O(\sqrt N)$ 解决吗？为什么要上筛法？后来仔细想，这个题的重点根本不在几何，而在把“整点计数”拆成“按范数 $n$ 统计表示个数 $r_2(n)$，再求前缀和”的过程。一旦你把问题看成积性函数前缀和，min_25筛就成了最顺手的工具。这篇文章不是官方题解的复述，而是我实际实现这道题时的完整复盘，包含公式推导、筛法代码、卡常细节，以及我在调试过程中遇到的各种坑。适合已经了解数论筛基础、想用 min_25筛 处理“不那么标准”函数的读者。

1. 题面拆解：从“数点”到“数积性函数”

1.1 用 $r_2(n)$ 把圆内整点重新表达

设 $r_2(n)$ 是满足 $x^2+y^2=n$ 的有序整数对 $(x,y)$ 的数量。那么圆内整点（包含原点）的答案可以写成

$$ 1+\sum_{n=1}^{N}r_2(n) $$

因为原点 $(0,0)$ 对应 $n=0$，剩下每个非零范数 $n$ 都有 $r_2(n)$ 个点。这个转换看起来简单，但它把二维几何区域变成了一个一维数论函数的累和。打个比方：你原本要在平面网格里画一个圆然后数点，现在只需要在一根数轴上逐个统计“范数为 $n$ 的格点有多少个”。

而 $r_2(n)$ 恰好有一个非常重要的结构：它是积性函数。从高斯整数 $\mathbb Z[i]$ 的角度看，$x+iy$ 的范数为 $n$，等价于把 $n$ 在 $\mathbb Z[i]$ 里分解成共轭素因子。最终可以推出经典的二平方和公式：

$$ r_2(n)=4\sum_{d\mid n}\chi_4(d) $$

其中 $\chi_4$ 是模 $4$ 的狄利克雷特征：偶数时为 $0$，$d\equiv1\pmod4$ 时为 $1$，$d\equiv3\pmod4$ 时为 $-1$。这是一个卷积 $1*\chi_4$ 再乘 $4$ 的结构，而 $1$ 和 $\chi_4$ 都是积性函数，所以 $r_2(n)$ 积性。

这里可以举两个例子帮助直觉。$r_2(5)=8$，因为 $(1,2),(2,1)$ 以及所有符号、交换组合共有 $8$ 个点；用公式算：$4(\chi_4(1)+\chi_4(5))=4(1+1)=8$。再看 $r_2(3)=0$，确实不存在整数解，公式给 $4(1+\chi_4(3))=4(1-1)=0$。这种“一个函数和它的所有因子有关”的结构，几乎就是在告诉我们应该用数论筛。

1.2 素数幂处的取值：min_25筛真正需要的表格

min_25筛要求 $f(p)$ 在素数处能拆成若干“完全积性函数”的线性组合，同时也要求 $f(p^k)$ 在递归算合数部分时能快速给出。因此我们需要把 $r_2(p^k)$ 的闭式列出来。直接由 $4\sum_{d\mid p^k}\chi_4(d)$ 计算，可以得到下面这张表：

解释一下为什么。$p=2$ 时，$\chi_4(2)=0$，所以整除 $2$ 的因子贡献全是 $0$，只剩下 $d=1$，因此 $r_2(2^k)=4$。$p\equiv1\pmod4$ 时，$\chi_4$ 在 $p^0,p^1,\dots,p^k$ 上恒为 $1$，因子贡献和为 $k+1$。$p\equiv3\pmod4$ 时，$\chi_4$ 在幂上交替为 $1,-1,1,-1,\dots$，累计和取决于 $k$ 的奇偶。

同时把素数处的取值单拎出来：$f(2)=4$，$f(p)=8$ 当 $p\equiv1\pmod4$，$f(p)=0$ 当 $p\equiv3\pmod4$。但我们不会直接用这种分段形式去维护 g 数组，而是把它改写成

$$ f(p)=4(1+\chi_4(p)) $$

因为 $\chi_4$ 在素数处完全由 $p\bmod4$ 决定，它本身是“完全积性函数”。把 $f(p)$ 拆成 $1$ 和 $\chi_4$ 两个完全积性函数的线性组合后，就可以用两套 g 数组分别筛，这正是 min_25筛 能处理这类题的关键。

1.3 为什么 $O(\sqrt N)$ 的做法在这里“不够用”

有人肯定会问：就是圆内整点，$O(\sqrt N)$ 明明很优秀，为什么还要 min_25筛？我在实际做题时也纠结过。如果只问最朴素的圆内点数，枚举 $x$ 从 $-\lfloor\sqrt N\rfloor$ 到 $\lfloor\sqrt N\rfloor$，累加 $2\lfloor\sqrt{N-x^2}\rfloor+1$，确实够快。

但一旦原题把统计对象升级一下，比如每一个整点还附带“按范数 $n$ 分类后统计 $n\equiv1\pmod4$ 的点数贡献”，或者把坐标从二维提升到四维，这种枚举法的复杂度就会指数膨胀，而积性函数前缀和的框架依然成立。而且从出题角度，绑定 min_25筛 往往意味着 $N$ 可以开到 $10^{10}\sim10^{12}$，在这种数据范围下，枚举法虽然常数小，但无法推广到带权、带模、多询问“按范数前缀和”的场景。所以我们这里就按照“把 $r_2(n)$ 前缀和作为核心任务”来展开，这是题目真正想考察的地方。

2. min_25筛选型：为什么是它而不是杜教筛

2.1 回顾 min_25筛 能处理哪一类函数

min_25筛 计算积性函数 $f$ 的前缀和 $\sum_{n\le N}f(n)$，要求 $f(p)$ 可以写成若干完全积性函数在素数处的值的线性组合，并且 $f(p^k)$ 能快速求值。为什么需要这两个条件？因为筛法前半部分只处理素数，后半部分的递归需要把合数项补回来。如果你在素数处无法拆解，那么质数部分的贡献就没法用一个统一的滚动数组维护；如果素数幂无法快速求值，那么合数部分就无法在递归时逐层累加。

恰好 $r_2(n)$ 两个条件都满足：$f(p)=4+4\chi_4(p)$，而 $\chi_4$ 是标准完全积性函数；$f(p^k)$ 有上一节那张表。于是 min_25筛 可以非常自然地套上去。

这里多说一句：min_25筛 的复杂度通常是 $O(N^{3/4}/\log N)$，实际实现时在 $N=10^{12}$ 量级需要处理约 $2\sqrt N$ 个离散点，也就是两百万个状态，完全可跑。

2.2 两个基础函数：质数个数与模4特征差

我们把 $f(p)$ 拆成 $4\cdot 1(p)+4\cdot\chi_4(p)$。对应到 min_25筛 的 g 数组，需要两个“种子函数”：

• $F_1(x)=x-1$，即 $2\sim x$ 的整数个数，筛完后变成 $\sum_{p\le x}1$。
• $F_2(x)=\sum_{i=2}^{x}\chi_4(i)$，筛完后变成 $\sum_{p\le x}\chi_4(p)$。

$F_2$ 的初始值看起来有点怪，但它本质上是“模4余1的正整数个数减去模4余3的正整数个数”。由于完整四个一循环的 $\chi_4$ 和为 $0$，$F_2(x)$ 只和 $x\bmod4$ 有关：余 $1$ 或余 $2$ 时为 $1$，余 $0$ 或余 $3$ 时为 $0$。注意这里的求和起点是 $2$，不能带上 $i=1$，因为 $1$ 不是素数，而且差分时会用到 $g(p-1)$，如果初始把 $1$ 算进去，后面所有质数贡献都会整体偏移。

在滚动筛的过程中，对当前质数 $p$，更新方式为：

$$ g_1(x)\leftarrow g_1(x)-\left(g_1(\lfloor x/p\rfloor)-g_1(p-1)\right) $$

$$ g_2(x)\leftarrow g_2(x)-\chi_4(p)\left(g_2(\lfloor x/p\rfloor)-g_2(p-1)\right) $$

这里 $g_2$ 的转移要乘 $\chi_4(p)$。当 $p=2$ 时乘 $0$，相当于不更新；这其实是正确的，因为 $F_2$ 初始已经把所有偶数贡献视为 $0$。当 $p=3$ 时 $\chi_4(3)=-1$，会把模4余3的质数的倍数从 $F_2$ 中削掉。

2.3 对比杜教筛与洲阁筛

写到这里，有人可能会问：杜教筛不行吗？我也试过。杜教筛需要构造辅助函数 $g$，使得 $fg$ 的前缀和容易计算。对 $r_2$ 本身，如果取 $g=1$，那么 $r_21$ 的前缀和

$$ \sum_{n\le N}\sum_{d\mid n}r_2(d)=\sum_{m\le N}\sum_{t\le N/m}r_2(t) $$

这里又会递归出现 $\sum r_2(t)$ 本身，等于绕回原点。虽然圆内整点有几何公式可以递归，但这个思路很难推广到带权或更一般的二次型情形。

洲阁筛理论上也能做，但它需要在多个维度上维护埃筛状态，代码复杂度比 min_25筛 高不少。我给一个简单的对比表：

所以最终我选择了 min_25筛，模板化程度高，调试起来也相对轻松。

3. 筛法实现：从预处理到递归求值的关键步骤

3.1 离散化：用 $\sqrt N$ 分块的 w 数组

min_25筛 第一步是把所有 $\lfloor N/i\rfloor$ 分块。设 $m$ 为不同取值的个数，数量大约是 $2\sqrt N$。实现时我用两个数组映射：

long long N, w[NM]; int id1[NM], id2[NM]; long long l = 1, r, v; while (l <= N) { v = N / l; w[++m] = v; if (v <= sq) id1[v] = m; else id2[N / v] = m; r = N / v; l = r + 1; }

这里的关键是：当 $v\le\sqrt N$ 时，直接用 $v$ 本身作为下标；当 $v>\sqrt N$ 时，用 $N/v$ 作为下标。因为此时 $N/v<\sqrt N$，所以 id2 数组大小也只要 $\sqrt N$ 量级。这个映射在滚动更新和递归求值中都要反复使用，我习惯写成一个内联函数：

inline int get_id(long long x) { return x <= sq ? id1[x] : id2[N / x]; }

3.2 g 数组的初始化和滚动

维护两个 g 数组，长度都是 $m$。初始化时：

long long chi_sum(long long x) { if (x < 2) return 0; long long r = x % 4; return (r == 1 || r == 2) ? 1 : 0; } for (int i = 1; i <= m; ++i) { g1[i] = w[i] - 1; g2[i] = chi_sum(w[i]); }

注意 $g_2$ 的初始值没有包含 $1$ 的贡献。这是我在第一次实现时踩的一个坑：如果把 $\chi_4(1)=1$ 算进去，后续所有素数差分都会多出 $1$，最终答案会整体偏移 $4$。

滚动循环的核心代码：

for (int k = 1; k <= cnt; ++k) { long long p = prime[k]; if (p * p > N) break; for (int i = 1; i <= m && w[i] >= p * p; ++i) { int id = get_id(w[i] / p); g1[i] -= g1[id] - g1[id1[p - 1]]; long long chi = chi_prime[k]; // 预处理：1, -1, 0 g2[i] = (g2[i] - chi * (g2[id] - g2[id1[p - 1]]) + MOD) % MOD; } }

这里 $p-1$ 一定小于 $\sqrt N$，所以可以直接用id1[p - 1]。注意w[i]是递减的，内层循环可以只跑到w[i] >= p^2，这是一个非常有效的常数优化。

3.3 S 递归：把合数部分拼回来

滚动全部结束后，$g_1[\text{get_id}(N)]$ 就是不超过 $N$ 的质数个数，$g_2[\dots]$ 就是质数集合上的 $\chi_4$ 和。于是素数部分的贡献是

$$ 4\left(g_1(x)-g_1(p_k)+g_2(x)-g_2(p_k)\right) $$

其中 $p_k$ 是当前限制的最小质数。但完整的 $\sum_{n\le N}r_2(n)$ 还要算合数。递归函数可以这样写：

long long dfs(long long x, int k) { long long res = 4 * ( (g1[get_id(x)] - g1[id1[prime[k]]] + MOD) % MOD + (g2[get_id(x)] - g2[id1[prime[k]]] + MOD) % MOD ) % MOD; for (int i = k + 1; i <= cnt; ++i) { long long p = prime[i]; if (p * p > x) break; long long pe = p; for (int e = 1; pe <= x / p; ++e, pe *= p) { long long cur = f_pe(p, e); // f(p^e) res = (res + cur * dfs(x / pe, i)) % MOD; res = (res + f_pe(p, e + 1)) % MOD; } } return res; }

其中f_pe根据前面表格实现：

long long f_pe(long long p, int e) { if (e == 0) return 1; if (p == 2) return 4; if (p % 4 == 1) return 4LL * (e + 1) % MOD; return (e % 2 == 0) ? 4 : 0; }

这里有个容易写错的地方：标准 min_25筛 的递归中，内层循环会对每个 $e$ 累加 $f(p^e)\cdot S(x/p^e,i)$，同时还要补上 $f(p^{e+1})$。这个 $f(p^{e+1})$ 是为了把“恰好包含 $e+1$ 次方质因子”的数也算进去。如果漏掉，所有含平方以上因子的大数都会少算一部分贡献。

最终答案就是：

long long ans = (dfs(N, 0) + 1) % MOD;

加 $1$ 是原点 $(0,0)$ 的贡献。

3.4 边界：原点、$n=1$ 和 $f$ 定义的一致性

有几个边界问题我在调试时反反复复确认过。

第一，dfs里的所有下标都要保证在get_id映射中能找到，尤其是递归调用dfs(x / pe, i)时，x / pe是一个新的离散点，必须用get_id获取下标。

第二，f_pe(p, 0)在递归中实际上不会被直接调用，但为了公式完整我保留下来了。在计算 $f(p^e)$ 时，$e$ 从 $1$ 开始，别从 $0$ 开始，否则会把 $1$ 重复计入。

第三，原点单独加 $1$ 的前提是题目允许 $(0,0)$。如果题面只统计正整数对或非零格点，这个 $1$ 要去掉或者改成别的边界条件。

第四，$f_2$ 的取值有正有负，但质数集合上的 $\chi_4$ 和可能很小，在取模时要注意负号。我全程用(a - b + MOD) % MOD来规范化，避免出现负数。

4. 实测过程中踩过的坑和性能调优

4.1 质数幂取值错误导致样例不对

我第一次实现时，把 $f(p)$ 直接设成“若 $p\equiv1\pmod4$ 则 $8$，否则 $4$”，然后偷懒在合数部分也沿用这个 $f(p)$，没有实现 $f(p^k)$ 的公式。结果样例全挂。比如 $n=25$，$r_2(25)$ 实际是 $12$，因为 $(3,4),(4,3)$ 加上符号交换共有 $8$ 个非零坐标点，再加上 $(\pm5,0),(0,\pm5)$ 共 $4$ 个点，总计 $12$。而我用错误写法只算出了 $8$。后来把 $f(p^k)$ 的表格单独抽出来写到f_pe里，才对上。

这个坑提醒我：min_25筛 之所以能“自动”处理合数，是因为递归时会把每个质因子幂次单独拿出来乘起来；如果你不在素数幂处提供正确的 $f$，那么所有含平方因子的数都会错。

4.2 模4特征差分和 $\chi_4(2)=0$ 的蝴蝶效应

$g_2$ 的滚动中，$p=2$ 时因为 $\chi_4(2)=0$，转移项乘 $0$ 等于不更新。如果不理解原因，很容易觉得这是 bug。实际上 $F_2(x)$ 的初始值已经把全部偶数贡献记为 $0$，2 的倍数在后续筛合数时本来就不应该有任何变化，所以跳过或执行等价。

但真正的蝴蝶效应在初始化。如果你把 $g_2[1]$ 设成 $\chi_4(1)=1$，那么每个质数差分都会多减一个 $1$，导致所有素数集合的 $\chi_4$ 和偏移，最后答案整体错乱。这个错误很难靠肉眼看出，因为单点小数据可能恰好算出来看着合理，一旦 $N$ 大到覆盖了各种模类，就全乱了。

所以我在写chi_sum时第一行就是if (x < 2) return 0;，宁可多写一个判断，也不让边界污染全局。

4.3 常数优化：从 3.2s 到 1.4s

我最初用unordered_map做离散点映射，$N=10^{12}$ 时总耗时约 $3.2s$。换成手写 id1/id2 数组后，降到约 $1.4s$。原因是 min_25筛 的内层循环被调用了很多次，哈希查找的代价被放大得非常明显。

另外两个常见优化：

• 预处理每个质数的chi_prime和p * p，避免在循环里反复计算%4。
• 滚动更新时利用 w 数组递减的性质，提前确定本次需要更新的最大下标，而不是每次都检查w[i] >= p * p。

还有一个关于递归的问题：有的题解会对dfs(x, k)做记忆化，但我在 $N=10^{12}$ 下实测收益不大，甚至更慢。因为递归状态数量本身没有到需要记忆化的规模，哈希开销反而拖累常数。如果你在 $N=10^{13}$ 或更大的数据上跑，可以再测一下，但不要盲目加记忆化。

4.4 防溢出小习惯

在pe <= x / p的判断里，用除法而不是乘法，避免long long溢出。在 g 数组差分时，g1[id] - g1[p-1]理论上不会溢出，但可能为负；g2更是正负交错，所以统一写成取模形式。我习惯把res相关的计算全部% MOD，而 g 数组本身用真实值存储。两种做法都可以，但混用最容易出 bug：如果 g 数组取模了，那质数个数可能变成负数；如果 g 数组不取模，那差值可能是负的，必须在最后规范化。选一种，写清楚，别来回改。

5. 从整点计数出发：还能扩展成哪些题

5.1 四平方和与带权二次型

如果问题改成四元组 $x^2+y^2+z^2+w^2\le N$，对应的 $r_4(n)$ 有经典公式

$$ r_4(n)=8\sum_{d\mid n,\ 4\nmid d}d $$

它依然是积性函数，且 $r_4(p)=8(1+p)$（$p=2$ 时特殊）。用 min_25筛 处理时，需要维护的种子函数变成 $\sum_{p\le x}1$ 和 $\sum_{p\le x}p$，因为素数处的线性组合是 $8+8p$。如果再加一个权重 $n^k$，那么种子函数就是自然数幂前缀和。$k$ 变大时，只需要多维护几维数组，框架完全不变。这就是为什么“整点计数”类题目经常和 min_25筛 绑定出现。

5.2 特征函数的线性组合：不局限于二次型

我们处理 $r_2$ 时，本质上是用 $1$ 和 $\chi_4$ 的线性组合覆盖了 $f(p)$。这个技巧可以推广到任何由狄利克雷卷积 $1*\chi$ 或若干特征函数乘积拼出的函数。比如 $\chi_3$、$\chi_{12}$，只要你能找到一组完全积性基 ${b_j(p)}$，使得

$$ f(p)=\sum_j c_j b_j(p) $$

min_25筛 就能处理。很多人以为 min_25筛 只能做 $n^k$ 型函数，实际上“完全积性函数”并不限定于多项式，模特征符号也是完全积性的。这道题就是最好的例子。

5.3 高维格点与近似高斯圆问题的关系

高维球内整点有个著名的渐近公式：主项是球的体积，但误差项很大。精确计数往往很困难。但如果我们按范数 $n$ 累加 $r_k(n)$，就回到了数论函数前缀和的视角。二维的 $r_2$ 前缀和近似于圆的面积，四维的 $r_4$ 前缀和近似于四维球的体积。直接用 $\pi R^2$ 这种公式只能给出近似值，而 min_25筛 可以精确计算到 $N=10^{12}$ 量级。几何枚举在高维下不可行，筛法的优势就体现出来了。

这也是为什么这类题会成为集训队题的常客：表面是几何，实际是让选手把几何对象翻译成积性函数，然后考验筛法的实现功底。

最后再分享一个我个人的习惯。做这类题时，我不会直接套模板，而是先把 $f(p)$ 的表格和对应的种子函数写在纸片上；如果 $f(p)$ 拆不出完全积性函数的线性组合，min_25筛 框架就会报废。这道“整点计数”最妙的地方，就是让你从 $r_2(n)$ 的几何定义一路推回 $\chi_4$，整个过程非常自然。如果你也想掌握 min_25筛 在非标准函数上的应用，强烈建议自己把这段代码逐行写一遍，然后把 $N$ 从 $10^6$ 一路测到 $10^{10}$，感受筛法在边界处的细微差异。踩过几个坑之后，再看这类题就会觉得“换汤不换药”了。