企业官网建设流程全解析

“类欧几里得算法”这个名字，我第一次看到时以为是欧几里得算法的花式改版，后来在洛谷 P5170 这类题里被它狠狠教育过一次：它和 gcd 的辗转相除只有“参数互换”这一点神似，核心其实是一套专门处理 $\sum \lfloor \frac{ai+b}{c}\rfloor$ 这类下取整求和的递归分治框架。如果你已经会 gcd 递归，又恰好被各种“数论分块搞不定的大范围求和”卡过，那这算法值得彻底搞懂。

这篇文章我尽量不用“显然”带过。你要的三个核心函数——一次和、平方和、带权下标和——分别怎么推、怎么码、怎么避坑，我都会写到，并且给出可直接对拍的模板。

1. 从“欧几里得”到“类欧几里得”：名字背后的同一个核心思路

欧几里得算法做 gcd，靠的是一个很朴素的观察：$\gcd(a,b)=\gcd(b,a\bmod b)$，把两个数不断变小，直到一方归零。类欧几里得算法也是一样，但它“变小”的不是两个数，而是一组求和参数。

我们先统一约定下面这类求和：

$$ f(n,a,b,c)=\sum_{i=0}^{n}\left\lfloor\frac{a\cdot i+b}{c}\right\rfloor $$

其中 $n\ge 0$，$c>0$，$a,b$ 可以是任意非负整数。注意这个式子里一共有 $n+1$ 项，$i$ 从 $0$ 取到 $n$。有些模板把求和范围写成 $i=0\sim n-1$，本质上只是指标偏移，不影响算法骨架，但你写代码前必须先看清楚自己的定义。

为什么这类求和难搞？因为 $\left\lfloor\frac{ai+b}{c}\right\rfloor$ 是个分段线性函数，$i$ 一大，硬算就是 $O(n)$，而竞赛题里 $n$ 常常是 $10^9$ 甚至 $10^{18}$。数论分块可以处理 $\sum \lfloor\frac{n}{i}\rfloor$，但对“线性函数除常数”这种形式就有点力不从心，因为分母是常量，分子的等差增量会让分块点变得不直观。

类欧几里得算法的策略很直接：先把分子里能整除 c 的部分拆出去，再把剩余的递归问题通过“翻转坐标轴”变成参数更小的问题。这个“翻转”就等价于欧几里得算法里的取模，于是递归层数天然被控制在 $\log$ 级别。

除了 $f$，很多题还会要求算平方和和带权下标和：

$$ g(n,a,b,c)=\sum_{i=0}^{n}\left\lfloor\frac{ai+b}{c}\right\rfloor^2 $$

$$ h(n,a,b,c)=\sum_{i=0}^{n} i\cdot \left\lfloor\frac{ai+b}{c}\right\rfloor $$

$f$ 是基础，$g,h$ 是它的两个“升级版”。难点在于 $g,h$ 不能独立递归，它们会互相纠缠，这也是模板代码看起来比预期长一圈的原因。

2. 主函数 f 的递推：能拆的整部先拆，剩下的交给翻转

2.1 第一个分支：a >= c 或 b >= c

当 $a\ge c$ 或 $b\ge c$ 时，可以把整数部分拆出来。设：

$$ a = q_a \cdot c + a_0,\quad 0\le a_0<c $$

$$ b = q_b \cdot c + b_0,\quad 0\le b_0<c $$

那么：

$$ \left\lfloor\frac{ai+b}{c}\right\rfloor = q_a\cdot i+q_b+\left\lfloor\frac{a_0 i+b_0}{c}\right\rfloor $$

对 $i$ 从 $0$ 到 $n$ 求和。这里出现了三个基本求和：

• $\sum_{i=0}^{n}1=n+1$
• $\sum_{i=0}^{n}i=\frac{n(n+1)}{2}$
• $\sum_{i=0}^{n}i^2=\frac{n(n+1)(2n+1)}{6}$

所以第一个分支是：

$$ f(n,a,b,c) = f(n,a_0,b_0,c)

• q_a\cdot\frac{n(n+1)}{2}
• q_b\cdot(n+1) $$

这一步很直观，但它重要在“消去”分子里能整除的部分，让下一步递归时能安心地做坐标翻转。很多初学者漏了 $b$ 这边，因为 $b\ge c$ 时b/c不是零，结果小范围还好，范围一大就差出常数项。

2.2 第二个分支：a < c 且 b < c 时的坐标翻转

现在分子小于分母了，不能再拆整数部分。设：

$$ m=\left\lfloor\frac{an+b}{c}\right\rfloor $$

如果 $m=0$，说明整个区间内每一项都取整成 $0$，$f=0$，直接返回。

否则，有一个很漂亮的恒等式：

$$ f(n,a,b,c)=n\cdot m-f(m-1,c,c-b-1,a) $$

这个式子怎么来的？几何上看，$\sum \lfloor\frac{ai+b}{c}\rfloor$ 是直线 $y=\frac{ai+b}{c}$ 下方的整点数量，$x$ 从 $0$ 到 $n$，$y$ 从 $1$ 到 $m$。把这堆点放进一个 $n\times m$ 的矩形里，你数下方点，剩下的就是上方点。把坐标轴“翻转”一下，上方点的数量刚好又是一个新的下取整求和，也就是 $f(m-1,c,c-b-1,a)$。

两个方向的点合起来正好铺满 $n\times m$ 个格子，于是得到上面那个 $f=n\cdot m-f(\cdots)$ 的式子。这也是“类欧几里得”名字的由来：每次递归都在做类似“取模”的参数缩小，递归的下一个问题是 $(m-1,c,c-b-1,a)$，而不再是原来的 $(n,a,b,c)$。

我们来验证一个小例子。取 $n=4,a=2,b=0,c=3$：

$$ \left\lfloor\frac{0}{3}\right\rfloor+\left\lfloor\frac{2}{3}\right\rfloor+\left\lfloor\frac{4}{3}\right\rfloor+\left\lfloor\frac{6}{3}\right\rfloor+\left\lfloor\frac{8}{3}\right\rfloor=0+0+1+2+2=5 $$

这里 $m=\lfloor8/3\rfloor=2$，递归计算：

$$ f(1,3,2,2)=\lfloor2/2\rfloor+\lfloor4/2\rfloor=1+2=3 $$

于是 $f=4\cdot2-3=5$，完全一致。

2.3 递归边界

只要分治到 $m=0$ 就可以返回。理论上当 $a=0$ 时，因为已经保证 $b<c$，$m=\lfloor b/c\rfloor=0$，会自然返回。所以代码里不需要单独讨论 $a=0$ 的边界，只需要在第二个分支开头检查 $n$ 和 $m$ 即可。

第一个分支可能让 $n=0$ 时仍需要计算，因为当 $b\ge c$ 时，$i=0$ 那一项本身就可能是非零的。这就是为什么模板里不要写“一进来就if(n==0) return 0”，应该先走整数拆分分支，再检查剩余问题的 $m$ 是否为 $0$。

3. g 与 h：平方和、带权和是怎么一起递推的

很多题不会只满足于让你算一次和，比如洛谷 P5170 就直接要求把 $f,g,h$ 三个一起输出。$g$ 和 $h$ 的推导思路和 $f$ 一样，但公式要复杂不少。

3.1 整除拆分分支下的 g 和 h

回到 $a=q_a c+a_0$、$b=q_b c+b_0$ 的拆法，记：

$$ u_i=\left\lfloor\frac{a_0 i+b_0}{c}\right\rfloor $$

则原下取整为：

$$ t_i=q_a\cdot i+q_b+u_i $$

平方展开：

$$ t_i^2 = q_a^2 i^2+q_b^2+u_i^2+2q_aq_b i+2q_a i u_i+2q_b u_i $$

把 $i=0\sim n$ 的求和整理出来，就得到：

$$ g(n,a,b,c) = g(n,a_0,b_0,c) +2q_a\cdot h(n,a_0,b_0,c) +2q_b\cdot f(n,a_0,b_0,c) $$

$$ +q_a^2\frac{n(n+1)(2n+1)}{6} +q_aq_b\cdot n(n+1) +q_b^2\cdot(n+1) $$

注意交叉项的系数：$2q_aq_b\sum i$ 化简后就是 $q_aq_b n(n+1)$，模板里别多乘一个 $2$。

$h$ 的展开更简单：

$$ t_i=q_a i+q_b+u_i $$

乘上 $i$ 后：

$$ i\cdot t_i=q_a i^2+q_b i+i\cdot u_i $$

所以：

$$ h(n,a,b,c) = h(n,a_0,b_0,c) +q_a\frac{n(n+1)(2n+1)}{6} +q_b\frac{n(n+1)}{2} $$

这里能看出为什么要同时维护三个量：$g$ 的递推需要用到 $h$，$g$ 和 $h$ 又都依赖 $f$。如果不把三个一起返回，只单独求 $g$ 会很难写。

3.2 坐标翻转分支下的 g 和 h

当 $a<c$、$b<c$ 时，设 $m=\lfloor(an+b)/c\rfloor$。$f$ 的翻转已经很漂亮，$g,h$ 的翻转更像是对同一批格点做二次计数。

先说结论：

$$ f(n,a,b,c)=n\cdot m-r_f $$

$$ g(n,a,b,c)=n\cdot m\cdot(m+1)-2r_h-2r_f-f(n,a,b,c) $$

其中 $r$ 表示子问题 $f(m-1,c,c-b-1,a)$ 对应的三个值，即：

$$ r_f=f(m-1,c,c-b-1,a) $$

$$ r_g=g(m-1,c,c-b-1,a) $$

$$ r_h=h(m-1,c,c-b-1,a) $$

再一个稍微需要点推导的：

$$ h(n,a,b,c)=\frac{n(n+1)}{2}m-\frac{r_g+r_f}{2} $$

这里最容易写错的是 $h$。网上有些流传版本的代码写的是 $n(n+1)/2\cdot m-r_f-r_h$，我印象里早期抄过这种写法，对拍小数据时偶尔会差一两个点。其实从“翻转坐标轴”的角度推一遍会发现：$h$ 本质是在数所有点的横坐标之和，翻转到子问题后，横坐标之和会借助“每列高度”再次求和，于是出现 $r_g$ 项。

我们用一个例子验证。还是 $n=4,a=2,b=0,c=3$：

• $t_i=0,0,1,2,2$
• $h=0\cdot0+1\cdot0+2\cdot1+3\cdot2+4\cdot2=16$

这里 $m=2$。子问题是 $f(m-1=1,c=3,c-b-1=2,a=2)$，在子问题里：

$$ u_j=\left\lfloor\frac{3j+2}{2}\right\rfloor=1,2 $$

所以：

• $r_f=1+2=3$
• $r_g=1^2+2^2=5$
• $r_h=0\cdot1+1\cdot2=2$

代入公式：

$$ h=\frac{4\cdot5}{2}\cdot2-\frac{3+5}{2}=20-4=16 $$

完全吻合。这个例子虽然小，但足够暴露公式里每次出现“除以 $2$”或“除以 $6$”时的整除问题。放心，数学上对应项都已经保证是整数，直接用整数除法即可，不用纠结。

3.3 递归顺序：先求 f，再求 g

注意到 $g(n,a,b,c)$ 的翻转公式右边出现了 $f(n,a,b,c)$ 本身。所以在代码里要先算：

res.f = n * m - r.f;

然后才能算：

res.g = n * m * (m + 1) - 2 * r.h - 2 * r.f - res.f;

这个顺序肉眼很难看出来，我第一次实现时把res.f写在后面，结果 $g$ 一直差一个奇怪的变量值，后来对拍才发现是“用到了还没算出来的原始 f”。

4. 标准模板：参数顺序、溢出防护与取模改造

我给的函数签名是：

Node calc(long long n, long long a, long long b, long long c)

返回三个值 $f,g,h$，其中求和范围是 $i=0\sim n$，一共 $n+1$ 项。如果你习惯“参数顺序是n, a, b, c”，往下看代码很顺；如果你习惯“n, m, a, b”这类英文来源模板，请先把顺序改统一，否则递归调用会错得莫名其妙。

4.1 未取模版本（理解用）

#include <bits/stdc++.h> using namespace std; struct Node { long long f, g, h; }; Node calc(long long n, long long a, long long b, long long c) { Node res, r; // 分支一：能拆的整数部分先拆出去 if (a >= c || b >= c) { long long qa = a / c, qb = b / c; r = calc(n, a % c, b % c, c); long long s0 = n + 1; // sum 1 long long s1 = n * (n + 1) / 2; // sum i long long s2 = n * (n + 1) * (2 * n + 1) / 6; // sum i^2 res.f = r.f + qa * s1 + qb * s0; res.g = r.g + 2 * qa * r.h + 2 * qb * r.f + qa * qa * s2 + qa * qb * n * (n + 1) // 等于 2*qa*qb*s1 + qb * qb * s0; res.h = r.h + qa * s2 + qb * s1; return res; } // 到这里保证 a < c, b < c if (n == 0) return {0, 0, 0}; __int128 m128 = ((__int128)a * n + b) / c; long long m = (long long)m128; if (m == 0) return {0, 0, 0}; // 分支二：坐标翻转 r = calc(m - 1, c, c - b - 1, a); res.f = n * (long long)m - r.f; res.g = n * (long long)m * (m + 1) - 2 * r.h - 2 * r.f - res.f; res.h = n * (n + 1) / 2 * (long long)m - (r.g + r.f) / 2; return res; }

这个版本只适合展示逻辑。真实的long long范围扛不住 $n=10^{18}$，n*m*(m+1)随便就爆出 $10^{54}$ 量级，必须取模或者使用大整数（Python 除外）。

4.2 改造为取模版本

竞赛里最常见的做法是边算边取模，比如模 $998244353$。因为公式里有除以 $2$、除以 $6$，所以需要预处理逆元：

• $inv2$ 可以取 $(MOD+1)/2$，或者用快速幂求 $2^{MOD-2}$。
• $inv6$ 用快速幂求 $6^{MOD-2}$。

取模版本里最关键的是把 $\frac{n(n+1)}{2}$ 写成n % MOD * ((n+1) % MOD) % MOD * inv2 % MOD，把 $\frac{n(n+1)(2n+1)}{6}$ 写成三个因子分别取模再乘 $inv6$。

翻转分支里的h = n*(n+1)/2*m - (r.g+r.f)/2，取模后写成：

res.h = ( (n % MOD) * ((n + 1) % MOD) % MOD * inv2 % MOD * (m % MOD) % MOD - ((r.g + r.f) % MOD) * inv2 % MOD + MOD ) % MOD;

这里分子保证是偶数，所以数学上 $\div 2$ 是整数；取模下用 $inv2$ 等价。如果你还想保留中间值的整除性，可以先把n*(n+1)算成 __int128 再除 $2$ 再取模，也能避免一些溢出纠结。

4.3 另一种常见模板：传引用返回

有些选手喜欢写成：

void calc(long long n, long long a, long long b, long long c, long long &f, long long &g, long long &h)

逻辑完全一样，只是把Node换成引用参数。我个人推荐用Node返回，可读性好，也方便递归。唯一要注意的是递归调用后，别把原始的a,b,c覆盖掉，否则后面的c-b-1会出错。

5. 复杂度：看似四个参数，实际递归层数只有 O(log)

单论每一层递归，做的都是常数次乘法、加法和一次递归调用。真正决定层数的是参数 $(a,c)$ 的变化过程。

看递归主体：

$$ (n,a,b,c) \rightarrow (m-1,; c,; c-b-1,; a) $$

新的分母是旧分子 $a$，新的分子是旧分母 $c$。这就像欧几里得算法里 $\gcd(a,c)$ 变成 $\gcd(c,a\bmod c)$ 一样，两个核心参数会互换并快速缩小。

我实际跑过几组极端数据，感受一下递归深度：

所以递归栈深度完全不用担心，真正要担心的是中间乘积的位数。比如n*m*(m+1)在未取模且数据为 $10^{18}$ 时会到 $10^{54}$ 量级，long long直接爆炸，所以要么取模，要么用大整数模板。

时间复杂度就是 $O(\log\max(a,c))$，而且因为每一步几乎不带常数因子，实际运行非常快。就算外层再套 $10^5$ 组询问，也完全可行。

6. 题型判断：什么时候该想到类欧几里得

学会公式后，更大问题是怎么认出一道题“该用类欧”。我总结出三个非常明显的信号。

6.1 信号一：求和表达式里出现线性下取整

最直接的形式是：

$$ \sum_{i=0}^{n}\left\lfloor\frac{a i+b}{c}\right\rfloor $$

只要 $n$ 大到 $10^9$ 以上，就不能暴力。先看能不能拆整、再看能不能翻转，基本就是类欧。

如果题目只求 $\sum \lfloor n/i\rfloor$，那用整除分块就行，不必上类欧。但一旦分子是 $ai+b$ 这种随 $i$ 线性增长的形式，整除分块的分段点会变得很不规律，类欧反而是更稳的解法。

6.2 信号二：几何里的直线下整点计数

计算一条斜率为 $a/c$ 的直线下方、$x\in[0,n]$ 范围内的整点个数，本质上就是：

$$ \sum_{i=0}^{n}\left(\left\lfloor\frac{ai+b}{c}\right\rfloor+1\right) $$

把常数项拆掉后就是 $f$ 加上 $n+1$。这类题经常伪装成“统计三角形内整点”“计算射线下方的点数量”等等，看到格点统计就要反应过来。

例如求 $\frac{a}{c}$ 斜率下、$y$ 截距为 $b/c$ 的直线与坐标轴围成区域内整点数，直接调calc(n, a, b, c).f就行。这在计算几何的某些格子题里能省掉一大段烦琐分类讨论。

6.3 信号三：需要二次和或加权和

当题目进一步要求“下取整的平方和”，或者给每个位置乘上 $i$ 再求和，比如：

$$ \sum i\cdot \lfloor\frac{ai+b}{c}\rfloor $$

这时模板里的 $g,h$ 就能直接用。常见套路是概率期望题里出现 $\lfloor\frac{...}{...}\rfloor^2$，数论题里出现 $i\cdot\lfloor...\rfloor$，如果你只写一个 $f$ 版本，会当场卡住。

这类信号组合起来，基本就能锁定类欧。剩下要做的就是把题目里的 $n,a,b,c$ 和边界条件对清楚，注意有些题下标从 $1$ 开始，那就要把 $i=0$ 的项单独减掉。

7. 我踩过的坑和对拍方法

这部分是全文里我觉得最“值钱”的部分。公式你能背，但“实际写对”是另一回事，尤其当你第一次从零实现时，下面几个坑几乎必踩。

7.1 坑一：递归子问题的参数顺序

第 2 节里翻转分支是：

calc(m - 1, c, c - b - 1, a)

我一开始写成：

calc(m - 1, a, c - b - 1, c)

看起来好像只是把 $a,c$ 位置换了一下，但在大范围数据上结果完全不对。因为公式推导时，新问题的“分子”是旧分母 $c$，“分母”是旧分子 $a$。你调换后，下一层递归的整除拆分就会进入错误的路径。

建议：写完核心代码后，立刻写一个暴力版：

def brute(n, a, b, c): return sum((a * i + b) // c for i in range(n + 1))

随机生成 $n\le 20$、$a,b,c\le 10$ 的数据，对拍几百组，参数顺序错的情况下第一组就能暴露出来。

7.2 坑二：g 的翻转分支依赖“原始 f”

res.g = n * m * (m + 1) - 2 * r.h - 2 * r.f - res.f;

这里的res.f必须是已经算好的原始 $f$。如果你先输出res.g再用res.f，编译器不会报错，但答案会错得很隐蔽。我建议在递归函数内部把代码顺序写成：

1. 算res.f
2. 算res.g
3. 算res.h

并在注释里标清楚。

7.3 坑三：n 的下标偏移

多数模板把求和写成：

$$ \sum_{i=0}^{n} $$

所以一共 $n+1$ 项。如果你看到某篇题解里s0 = n + 1，那是 0 起点的写法；如果看到s0 = n，那是 1 起点或“项数”写法。两种写法在递归公式里会引发连环差异，尤其第二个分支里的n*m会差一个 $m$。

最稳的办法：先明确自己题目的下标范围，再用暴力对拍验证。不要凭记忆改公式。

7.4 坑四：取模版直接除了再取模

当你要输出模 $MOD$ 结果时，不能先把未取模的res.g算出来再取模，因为那个未取模值早就溢出了。应该在每步都用取模乘法和逆元。

但有个例外：翻转分支里形如 $(r.g+r.f)/2$ 的式子，如果你刚好有未取模版本的r.g、r.f，可以直接整除，因为 $u_j(u_j+1)$ 是偶数。用取模版本时，就要用(r.g + r.f) % MOD * inv2 % MOD。这两者在数学上等价，写之前想清楚自己在用哪套代码。

7.5 对拍思路参考

我的标准对拍流程：

1. 写一个暴力函数，$O(n)$ 直接求和。
2. 写一个类欧函数，用long long处理小范围。
3. 随机生成 $n\in[0,50]$，$a,b,c\in[1,20]$，比较f,g,h三个值，连续跑 2000 组。
4. 全部通过后，再把a,b,c随机到 $10^9$，只验证f和暴力分块结果是否一致，g,h则用模版样例或题目数据验证。

对拍能救回无数个“看似正确的公式错误”。我强烈建议这篇文章里的推导你读完后，亲手复现一遍这个对拍，比背十遍模板都有效。

最后分享一个小习惯

我后来写类欧相关题时，习惯先把三个公式抄在一张纸上，再对着公式写代码，而不是对着网上的模板改参数。因为模板风格太多，有的是n下标偏移，有的是参数顺序不同，抄错一个符号很难排查。只要公式在手，代码顺序跟着推导走，出问题也知道去哪一行找。

如果下一篇博客还有机会，我想专门聊聊类欧在“扩展欧几里得+同余方程”里的配合用法：有些数论题会同时出现 $\sum \lfloor\frac{ai+b}{c}\rfloor$ 和 $\sum i^2\lfloor...\rfloor$，那就要额外扩展到四阶和。不过只要把今天这套“拆整+翻转”的思路吃透，任何高阶变体都是同样套路，只是代数展开活更多而已。