前缀和)
“整点计数”这四个字放在数论题里总会让人产生一种“这是几何题”的错觉。我第一次看到这道题时题面只有一句话给定 $N$求所有满足 $x^2y^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^2y^2n$ 的有序整数对 $(x,y)$ 的数量。那么圆内整点包含原点的答案可以写成$$ 1\sum_{n1}^{N}r_2(n) $$因为原点 $(0,0)$ 对应 $n0$剩下每个非零范数 $n$ 都有 $r_2(n)$ 个点。这个转换看起来简单但它把二维几何区域变成了一个一维数论函数的累和。打个比方你原本要在平面网格里画一个圆然后数点现在只需要在一根数轴上逐个统计“范数为 $n$ 的格点有多少个”。而 $r_2(n)$ 恰好有一个非常重要的结构它是积性函数。从高斯整数 $\mathbb Z[i]$ 的角度看$xiy$ 的范数为 $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(11)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)$ 计算可以得到下面这张表素数类型$r_2(p^k)$$p2$$4$$p\equiv1\pmod4$$4(k1)$$p\equiv3\pmod4$$k$ 为偶数时 $4$$k$ 为奇数时 $0$解释一下为什么。$p2$ 时$\chi_4(2)0$所以整除 $2$ 的因子贡献全是 $0$只剩下 $d1$因此 $r_2(2^k)4$。$p\equiv1\pmod4$ 时$\chi_4$ 在 $p^0,p^1,\dots,p^k$ 上恒为 $1$因子贡献和为 $k1$。$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}\rfloor1$确实够快。但一旦原题把统计对象升级一下比如每一个整点还附带“按范数 $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)44\chi_4(p)$而 $\chi_4$ 是标准完全积性函数$f(p^k)$ 有上一节那张表。于是 min_25筛 可以非常自然地套上去。这里多说一句min_25筛 的复杂度通常是 $O(N^{3/4}/\log N)$实际实现时在 $N10^{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_{i2}^{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$不能带上 $i1$因为 $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)$。当 $p2$ 时乘 $0$相当于不更新这其实是正确的因为 $F_2$ 初始已经把所有偶数贡献视为 $0$。当 $p3$ 时 $\chi_4(3)-1$会把模4余3的质数的倍数从 $F_2$ 中削掉。2.3 对比杜教筛与洲阁筛写到这里有人可能会问杜教筛不行吗我也试过。杜教筛需要构造辅助函数 $g$使得 $fg$ 的前缀和容易计算。对 $r_2$ 本身如果取 $g1$那么 $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筛 高不少。我给一个简单的对比表方法适用条件对 $r_2$ 的适配代码实现杜教筛能找到辅助 $g$弱需要额外几何公式中洲阁筛广泛可做但复杂难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^{e1})$。这个 $f(p^{e1})$ 是为了把“恰好包含 $e1$ 次方质因子”的数也算进去。如果漏掉所有含平方以上因子的大数都会少算一部分贡献。最终答案就是long long ans (dfs(N, 0) 1) % MOD;加 $1$ 是原点 $(0,0)$ 的贡献。3.4 边界原点、$n1$ 和 $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)$ 的公式。结果样例全挂。比如 $n25$$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$ 的滚动中$p2$ 时因为 $\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做离散点映射$N10^{12}$ 时总耗时约 $3.2s$。换成手写 id1/id2 数组后降到约 $1.4s$。原因是 min_25筛 的内层循环被调用了很多次哈希查找的代价被放大得非常明显。另外两个常见优化预处理每个质数的chi_prime和p * p避免在循环里反复计算%4。滚动更新时利用 w 数组递减的性质提前确定本次需要更新的最大下标而不是每次都检查w[i] p * p。还有一个关于递归的问题有的题解会对dfs(x, k)做记忆化但我在 $N10^{12}$ 下实测收益不大甚至更慢。因为递归状态数量本身没有到需要记忆化的规模哈希开销反而拖累常数。如果你在 $N10^{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^2y^2z^2w^2\le N$对应的 $r_4(n)$ 有经典公式$$ r_4(n)8\sum_{d\mid n,\ 4\nmid d}d $$它依然是积性函数且 $r_4(p)8(1p)$$p2$ 时特殊。用 min_25筛 处理时需要维护的种子函数变成 $\sum_{p\le x}1$ 和 $\sum_{p\le x}p$因为素数处的线性组合是 $88p$。如果再加一个权重 $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筛 可以精确计算到 $N10^{12}$ 量级。几何枚举在高维下不可行筛法的优势就体现出来了。这也是为什么这类题会成为集训队题的常客表面是几何实际是让选手把几何对象翻译成积性函数然后考验筛法的实现功底。最后再分享一个我个人的习惯。做这类题时我不会直接套模板而是先把 $f(p)$ 的表格和对应的种子函数写在纸片上如果 $f(p)$ 拆不出完全积性函数的线性组合min_25筛 框架就会报废。这道“整点计数”最妙的地方就是让你从 $r_2(n)$ 的几何定义一路推回 $\chi_4$整个过程非常自然。如果你也想掌握 min_25筛 在非标准函数上的应用强烈建议自己把这段代码逐行写一遍然后把 $N$ 从 $10^6$ 一路测到 $10^{10}$感受筛法在边界处的细微差异。踩过几个坑之后再看这类题就会觉得“换汤不换药”了。 
长河君 · 2026/10/17 1:32:11 · 阅读 1.2k 圆内整点计数：用min_25筛处理r_2(n)前缀和
“整点计数”这四个字放在数论题里总会让人产生一种“这是几何题”的错觉。我第一次看到这道题时题面只有一句话给定 $N$求所有满足 $x^2y^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^2y^2n$ 的有序整数对 $(x,y)$ 的数量。那么圆内整点包含原点的答案可以写成$$ 1\sum_{n1}^{N}r_2(n) $$因为原点 $(0,0)$ 对应 $n0$剩下每个非零范数 $n$ 都有 $r_2(n)$ 个点。这个转换看起来简单但它把二维几何区域变成了一个一维数论函数的累和。打个比方你原本要在平面网格里画一个圆然后数点现在只需要在一根数轴上逐个统计“范数为 $n$ 的格点有多少个”。而 $r_2(n)$ 恰好有一个非常重要的结构它是积性函数。从高斯整数 $\mathbb Z[i]$ 的角度看$xiy$ 的范数为 $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(11)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)$ 计算可以得到下面这张表素数类型$r_2(p^k)$$p2$$4$$p\equiv1\pmod4$$4(k1)$$p\equiv3\pmod4$$k$ 为偶数时 $4$$k$ 为奇数时 $0$解释一下为什么。$p2$ 时$\chi_4(2)0$所以整除 $2$ 的因子贡献全是 $0$只剩下 $d1$因此 $r_2(2^k)4$。$p\equiv1\pmod4$ 时$\chi_4$ 在 $p^0,p^1,\dots,p^k$ 上恒为 $1$因子贡献和为 $k1$。$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}\rfloor1$确实够快。但一旦原题把统计对象升级一下比如每一个整点还附带“按范数 $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)44\chi_4(p)$而 $\chi_4$ 是标准完全积性函数$f(p^k)$ 有上一节那张表。于是 min_25筛 可以非常自然地套上去。这里多说一句min_25筛 的复杂度通常是 $O(N^{3/4}/\log N)$实际实现时在 $N10^{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_{i2}^{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$不能带上 $i1$因为 $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)$。当 $p2$ 时乘 $0$相当于不更新这其实是正确的因为 $F_2$ 初始已经把所有偶数贡献视为 $0$。当 $p3$ 时 $\chi_4(3)-1$会把模4余3的质数的倍数从 $F_2$ 中削掉。2.3 对比杜教筛与洲阁筛写到这里有人可能会问杜教筛不行吗我也试过。杜教筛需要构造辅助函数 $g$使得 $fg$ 的前缀和容易计算。对 $r_2$ 本身如果取 $g1$那么 $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筛 高不少。我给一个简单的对比表方法适用条件对 $r_2$ 的适配代码实现杜教筛能找到辅助 $g$弱需要额外几何公式中洲阁筛广泛可做但复杂难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^{e1})$。这个 $f(p^{e1})$ 是为了把“恰好包含 $e1$ 次方质因子”的数也算进去。如果漏掉所有含平方以上因子的大数都会少算一部分贡献。最终答案就是long long ans (dfs(N, 0) 1) % MOD;加 $1$ 是原点 $(0,0)$ 的贡献。3.4 边界原点、$n1$ 和 $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)$ 的公式。结果样例全挂。比如 $n25$$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$ 的滚动中$p2$ 时因为 $\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做离散点映射$N10^{12}$ 时总耗时约 $3.2s$。换成手写 id1/id2 数组后降到约 $1.4s$。原因是 min_25筛 的内层循环被调用了很多次哈希查找的代价被放大得非常明显。另外两个常见优化预处理每个质数的chi_prime和p * p避免在循环里反复计算%4。滚动更新时利用 w 数组递减的性质提前确定本次需要更新的最大下标而不是每次都检查w[i] p * p。还有一个关于递归的问题有的题解会对dfs(x, k)做记忆化但我在 $N10^{12}$ 下实测收益不大甚至更慢。因为递归状态数量本身没有到需要记忆化的规模哈希开销反而拖累常数。如果你在 $N10^{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^2y^2z^2w^2\le N$对应的 $r_4(n)$ 有经典公式$$ r_4(n)8\sum_{d\mid n,\ 4\nmid d}d $$它依然是积性函数且 $r_4(p)8(1p)$$p2$ 时特殊。用 min_25筛 处理时需要维护的种子函数变成 $\sum_{p\le x}1$ 和 $\sum_{p\le x}p$因为素数处的线性组合是 $88p$。如果再加一个权重 $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筛 可以精确计算到 $N10^{12}$ 量级。几何枚举在高维下不可行筛法的优势就体现出来了。这也是为什么这类题会成为集训队题的常客表面是几何实际是让选手把几何对象翻译成积性函数然后考验筛法的实现功底。最后再分享一个我个人的习惯。做这类题时我不会直接套模板而是先把 $f(p)$ 的表格和对应的种子函数写在纸片上如果 $f(p)$ 拆不出完全积性函数的线性组合min_25筛 框架就会报废。这道“整点计数”最妙的地方就是让你从 $r_2(n)$ 的几何定义一路推回 $\chi_4$整个过程非常自然。如果你也想掌握 min_25筛 在非标准函数上的应用强烈建议自己把这段代码逐行写一遍然后把 $N$ 从 $10^6$ 一路测到 $10^{10}$感受筛法在边界处的细微差异。踩过几个坑之后再看这类题就会觉得“换汤不换药”了。