数论笔记：类欧几里得算法的盛宴

· · 个人记录

类欧几里得算法

类欧还挺难的，但是很有意思，我尽量用最浅显的语言来描述，不懂得评论区提出。

那么，我们来学习一下最基本的类欧吧。

【提高】类欧几里得算法基础

更新日志

所求大意

基本题意就是，给定 a,b,c,n，求：

\sum_{x=0}^{n}\left\lfloor\dfrac{ax+b}{c}\right\rfloor

以几何的角度来理解就是“求直线在给定区间下包含整点的个数”。

首先，将其写成普通函数的形式：

f(a,b,c,n)=\sum_{x=0}^{n}\left\lfloor\dfrac{ax+b}{c}\right\rfloor

那么我们接下来的任务就是化简了。

取模化简

化简意义：能够将 a\ge c 或 b\ge c 的情况转化为 a,b<c 的情况。

首先我们可以将 a 拆分为 (a\bmod c)+(a-a\bmod c)，同样，b 也可这样处理，分为 (b\bmod c)+(b-b\bmod c)，这样，对于包含 a 的这一项我们可以将 x 提取出来，利用乘法分配律很容易得出：

f(a,b,c,n)=\sum_{x=0}^{n}\left\lfloor\dfrac{(a\bmod c)x+(a-a\bmod c)x+(b\bmod c)+(b-b\bmod c)}{c} \right\rfloor

这时候我们会发现要进一步化简其实很容易，因为我们知道对于任意的 \dfrac{t_0+t_1}{t_2}=\dfrac{t_0}{t_2}+\dfrac{t_1}{t_2}，所以我们可以对上述的柿子做同样的处理，将对 c 取模的部分合并，同时将剩下的部分也合并：

f(a,b,c,n)=\sum_{x=0}^{n}\left\lfloor\dfrac{(a \bmod c)x + (b \bmod c)}{c}\right\rfloor+\dfrac{(a-a\bmod c)x}{c}+\dfrac{b-b \bmod c}{c}

注意，由于取余后剩下的部分一定能被 c 整除，所以不需要加上下取整的括号，于是我们就能够成功的将其拆成几个部分。

这时思考一下，是否一定存在：

\left\lfloor\dfrac{a}{c}\right\rfloor=\dfrac{a-(a\bmod c)}{c}

事实上，这样的一个化简就是利用“下取整忽略余数部分”的一个思想，达成去掉取余符号的目的，那么对于 a 和 b 的相关柿子都进行类似的处理，我们就可以得到：

\sum_{x=0}^{n}\left\lfloor\dfrac{(a\bmod c)x+(b\bmod c)}{c}\right\rfloor+\left\lfloor\dfrac{a}{c}\right\rfloor x+\left\lfloor\dfrac{b}{c}\right\rfloor

对于那个含有 a 的部分，由于存在 x（作为循环变量），我们可以用高斯求和公式得出其总和，同样的，对于不存在循环变量作为系数的 b 相关柿子，我们也可以简单的化简为：

\left(\dfrac{n(n+1)}{2}\cdot\left\lfloor\dfrac{a}{c}\right\rfloor+n\left\lfloor\dfrac{b}{c}\right\rfloor \right)+\sum_{x=0}^{n}\left\lfloor\dfrac{(a\bmod c)x+(b\bmod c)}{c}\right\rfloor

然后我们再将其求和部分写成最初定义的基本函数形式：

\frac{n(n+1)}{2}\left\lfloor\dfrac{a}{c}\right\rfloor+n\left\lfloor\dfrac{b}{c}\right\rfloor+f(a\bmod c,b\bmod c,c,n)

这样的一个作用是我们能够将函数中 a 和 b（注意，不是原式中的常量，而是右半部分函数的参数）写成 a<c 且 b<c 的形式（显然取模是保证了这一作用），那么我们就可以进行其他的操作了。

好的，我们的化简暂告一段落。

贡献化简

化简意义：形成“辗转相除”的形式，使得数量级递减，达到 O(\log n) 的复杂度。

怎么说呢，接下来这一部分有些困难，一定要仔细理解。

我们很容易可以理解的一个想法是，对于：

\sum\limits_{x=0}^{n}\left\lfloor\dfrac{ax+b}{c}\right\rfloor

来说，x\le n 是条件，而 \left\lfloor\dfrac{ax+b}{c}\right\rfloor 是这个循环的贡献，他很容易就可以化简为这样的式子：

\left\lfloor\dfrac{ax+b}{c}\right\rfloor=1\cdot\left\lfloor\dfrac{ax+b}{c}\right\rfloor

那么我们不妨将他改为条件，而贡献用作 1，这样整理出来的式子如下：

\left\lfloor\dfrac{ax+b}{c}\right\rfloor=\sum\limits_{j=0}^{\left\lfloor\frac{ax+b}{c}\right\rfloor-1}1

之所以条件要减一，因为我们将循环变量从 0 开始了，所以原式我们就可以简化为：

\sum\limits_{x=0}^{n}\sum\limits_{j=0}^{\left\lfloor\frac{ax+b}{c}\right\rfloor-1}1

大家可以发现一种神奇的现象，在 j 的式子条件中，会改变的值只有 x 一个，所以我们可以说“x 限制了 j 的上界”，而我们用类似的思想就可以看出来 n 限定了 x 的上界。

那么我们就可以用一种非常简单的办法来解决了，由于调换两个式子的顺序是不会影响他们的结果，所以我们可以通过调整顺序来使得 x 和 j 都被 n 限制，这有利于我们后面继续化简：

\sum\limits_{j=0}^{\left\lfloor\frac{ax+b}{c}\right\rfloor-1}\sum\limits_{x=0}^{n}\left[j<\left\lfloor\dfrac{ax+b}{c}\right\rfloor\right]

注意，对于一个包含（类）逻辑表达式的中括号（如下）：

\left[j<\left\lfloor\dfrac{ax+b}{c}\right\rfloor\right]

当中括号内的逻辑式成立时，其值为 1，反之为 0，我们称其为的谓词函数，而这样的一个方式能让他在正确的时候做出正确的贡献（想一想，为什么），相当于限制了循环变量的范围。

不过还需要注意，外面是中括号，中间的括号是下取整符号，注意他们长相的差别。然后，我们可以利用不等式的一些独特特性，来对谓词函数内的柿子做一定简单的处理，如下：

j<\left\lfloor\dfrac{ax+b}{c}\right\rfloor

由于我们知道 j 一定是整数，同时不等式的右半边由于下取整的符号存在，也一定是整数，那么我们就可以认为两边的差距至少为 1，由此可以推出：

j+1\le\left\lfloor\dfrac{ax+b}{c}\right\rfloor

由于下取整过后的结果一定小于等于原数，所以我们可以进一步去掉下取整符号：

j+1\le\dfrac{ax+b}{c}

接着，由于已知 c 一定是正整数（注意存在正这个条件），所以两边同时乘 c 得到：

cj+c\le ax+b

按照我们已经学过的不等式法则，一通变换易得：

cj+c-b\le ax\quad\to\quad cj+c-b-1<ax

最后，再次进行下取整就可以得到：

\left\lfloor\dfrac{cj+c-b-1}{a}\right\rfloor<x

这时候，我们利用不等式和下取整的一些特性，严格将 x 消除（或者说减少了 x 对于整个柿子的影响），所以之后的“限制”就可以直接用这个式子进行化简。

这时候，为了在之后的表达更为简便，我们引入新变量，令 m=\left\lfloor\dfrac{ax+b}{c}\right\rfloor，我们就可以继续化简：

f(a,b,c,n)=\sum\limits_{j=0}^{m-1}\sum\limits_{x=0}^{n}\left[x>\left\lfloor\dfrac{cj+c-b-1}{a}\right\rfloor\right]

这时候我们发现第二重求和是可以化简的，由于他的贡献简单，所以接着简化循环就可以写出来一个简单的式子（并且也把谓词函数消除了）：

f(a,b,c,n)=\sum\limits_{j=0}^{m-1}\left(n-\left\lfloor\dfrac{cj+c-b-1}{a}\right\rfloor\right)

我们把 n 对整个式子的贡献单独拿出来，其他再算：

f(a,b,c,n)=n\cdot m\sum\limits_{j=0}^{m-1}\left\lfloor\dfrac{cj+c-b-1}{a}\right\rfloor

那么，似乎不能再（或者说不必要）进一步简化柿子了，这时候我们仔细观察就能发现，最后一部分的柿子和我们一开始的定义有亿点点相似，那么能不能把他写成递归的形式呢？

我们再来看看定义：

f(a,b,c,n)=\sum_{x=0}^{n}\left\lfloor\dfrac{ax+b}{c}\right\rfloor

如果要写成基本柿子，那么必须要将两个柿子的元素对应起来。显然可以注意到的是，在这样的一个函数中存在的对应有：

如果我们将 c-b-1 看成一个整体，那么还存在：

同样的，我们如果只对 a 和 c 进行观察，我们会发现他们的位置互换了。互换之后大小关系也就相反，如果再进行第一次的取膜化简，就容易将其数量级大大减小。那么，求和过程中的 n 能不能拿出来计算呢？

第一部分的 n 一共计算了 m 次，即循环 m 次每次贡献为 n，所以他对于整个柿子的贡献是 n\cdot m，而最后我们将后面的式子用函数的形式写出来就是：

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

好的，我们已经将这样一个柿子进行了长足的化简，剩下的就只有实现了！那么我们应该怎样对一个普通的式子进行处理呢？事实上，我们必须要清楚，两种不同的化简并非随意使用，而是两种特定的情况下使用的，这样交替化简，就很容易根据我们已经证明过的内容得出：

\frac{n(n+1)}{2}\left\lfloor\dfrac{a}{c}\right\rfloor+n\left\lfloor\dfrac{b}{c}\right\rfloor+f(a\bmod c,b\bmod c,c,n) f(a,b,c,d)=n\cdot m-f(c,c-b-1,a,m-1)

第一个柿子是对于 a\ge c 或 b\ge c 情况的化简，能使他变成第二个情况，好进行递归化简。

而正是这样的一个递归形式的式子，我们反复的递归调用就可以将 c 和 a 调换并缩小，从而一步步减少数量级，观察一下代码并做一个粗略的评估，可以感性地看出这个柿子可以用 O(\log n) 的复杂度做到函数求和。

反复调换缩小数量级的过程，其实特别像求最大公约数的过程，也就是欧几里得算法（辗转相除法）：

\gcd(a,b)=\gcd(b,a \bmod b)

所以，这样的一个“求值过程类似于欧几里得算法的算法”，我们称之为“类欧几里得算法”。

就这样，我们完成了完整的推导。

代码实现

事实上，我们要注意一点：

版本一：求的范围为 1\sim n-1

你会发现这个版本是在直接模拟我们第一次求出来的内容，同时将后半部分进行了替换，我是用它 AC 了“求不出的等式”一题。

然而这个式子也的确很迷惑，我也不大能理解，所以感性看看吧。

int f(int a,int b,int c,int n) {
    if(n<=0)return 0;
    return n*(n-1)/2*(a/c)+n*(b/c)+f(c,(a*n+b)%c,a%c,(a%c*n+b%c)/c);
}

版本二：正式模板

这个模板是正确的，且在多道题目都测试过了，应该没有问题。可以说是忠实的按照我们最后的推导来实现了。

int f(int a,int b,int c,int n){
    if(a==0)return((b/c)*(n+1));
    if(a>=c||b>=c)return f(a%c,b%c,c,n)+(a/c)*n*(n+1)/2+(b/c)*(n+1);
    int m=(a*n+b)/c;
    return n*m-f(c,c-b-1,a,m-1);
}

后记：我为什么写学习笔记

其实，我特别享受一个分享和总结的过程。

真正的学习是永无止境的，你的笔记可能真的没什么人看，可能写的粗糙，还可能有学术错误——但是这样一个不断完善、修改和重构的过程中，你才能更深入的对算法和知识有自己的理解，正如同你没有亲手打过调过 pushup 就不会深刻的知道线段树怎么实现；正如你没有一步步推导过欧拉恒等式的柿子，也不会知道他究竟为什么美，为什么那么有魅力；而学习笔记，正是自己的一本日记本，所有的心酸和快乐，都共存于此，这是一本属于 OI 的回忆录。

梦想路上，也不是所有的努力都会奏效，同样的，学习算法的过程中也不会总是一帆风顺。我想，走过这么多的坎坷，才能知道，无论算法还是自己，“为什么这样”，“怎么才可以这样”，“都将会怎么样”；也就是过去、现在和未来。

正所谓“在 OI 中，更重要的是怎样求的更快，而不是怎样求”，这样的一个推导的过程，与我来说是优美的，更像是一场盛宴，遇到困难和挫折，自己思考解决，和大家探讨——写学习笔记的过程，其实就像是和一个个算法约会，更深入他们的内心，才能成为一个合格的 OIer。

其实，我们的每一份努力，都不必存在理由。

最后，感谢大家的阅读，点个赞好吗？