类欧几里得算法学习笔记

类欧几里得算法

因为柿子较长所以本文推荐全屏阅读

是什么 ：

类欧几里德算法是由洪华敦在 2016 年冬令营营员交流中提出的内容，其本质可以理解为，使用一个类似辗转相除法来做函数求和的过程。

为什么 ：

因为要考，可以用来解决一些计数问题，尤其是遇到下取整符号时。

能在计数的求和中避免运算和式而转化成递归，把一个 $O(n)$ 直接降成 $O(\log n)$ 真的是太强大了。

一般形式的代码很好写，或许可以拿来爆标（

怎么做 ：

就推柿子就完了，没什么难的.

比如这里先放一个oi——wiki的链接 ： 类欧几里德算法

step1 :

求：

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

首先，设 ：

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

其中$a$,$b$,$c$,$n$都是已知的常数，类欧几里得算法可以做到在$O (\text{log n} )$
的时间内求出答案
那么简单的化一下柿子：

$$\begin{aligned} f(a, b, c, n) &=\sum_{i=0}^{n}\left\lfloor\frac{a i+b}{c}\right\rfloor \\ &=\sum_{i=0}^{n}\left\lfloor\frac{\left(\left\lfloor\frac{a}{c}\right\rfloor c+a \bmod c\right) i+\left(\left\lfloor\frac{b}{c}\right\rfloor c+b \bmod c\right)}{c}\right\rfloor \\ &=\frac{n(n+1)}{2}\left\lfloor\frac{a}{c}\right\rfloor+(n+1)\left\lfloor\frac{b}{c}\right\rfloor+\sum_{i=0}^{n}\left\lfloor\frac{(a \bmod c) i+(b \bmod c)}{c} \right\rfloor \\ &=\frac{n(n+1)}{2}\left\lfloor\frac{a}{c}\right\rfloor+(n+1)\left\lfloor\frac{b}{c}\right\rfloor+f(a \bmod c, b \bmod c, c, n) \end{aligned}$$

接下来就可以递归求解了——但是！
我们发现当a，b满足 $a < c,b < c$ 时，程序会直接陷入无限递归——显然以上递归式对 $a < c,b < c$ 不适用
其实a,b 满足$a \ge c \ \&\&\ b \ge c \ $的情况大概是学过的三种类欧柿子里头最简单的情况。
那么，就可以再推一个柿子（
长期的推柿子经验告诉我们，要把$\sum$后边的东西提到$\sum$上边当条件，那么，可以得到：

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

推柿子的经验又告诉我们： 要把枚举 $\ j\ $ 提前
所以我们设一个 $m = \left \lfloor \frac{an+b}{c} \right \rfloor - 1$ 作为 $j$ 的枚举上界
那么就是 ：

$$\sum_{j = 0}^{m} \sum_{i=0}^{n} \left [ j < \left \lfloor \frac{ai+b}{c} \right \rfloor \right ]$$

大眼观察法可以得出 ：$ j < \left \lfloor \frac{ai+b}{c} \right \rfloor $ 这个东西看起来似乎大有可为
我们考虑想办法去掉其中的下取整符号——放缩
那么就有

$$j < \left \lfloor \frac{ai+b}{c} \right \rfloor \Longleftrightarrow j+1 \le \left \lfloor \frac{ai+b}{c} \right \rfloor \Longleftrightarrow j+1 \le \frac{ai+b}{c}$$ $$\Longleftrightarrow jc+c \le ai+b \Longleftrightarrow jc+c-b \le ai$$ $$\Longleftrightarrow jc+c-b-1 < ai \Longleftrightarrow \left \lfloor \frac{jc+c-b-1}{a} \right \rfloor < i$$

那么经过了以上的放缩变换之后，现在的柿子化为 ：

$$\sum_{j = 0}^{m} \sum_{i=0}^{n} \left [ i > \left \lfloor \frac{jc+c-b-1}{a} \right \rfloor \right ]$$

于是我们就可以消掉变量$i$了（！）
也就是 ：

$$\sum_{j = 0}^{m}(n - \left \lfloor \frac{jc+c-b-1}{a} \right \rfloor )$$

(正确性显然）
拆开这个 $\sum$ 也就是 ：

$$\sum_{j = 0}^{m}n - \sum_{j = 0}^{m} \left \lfloor \frac{jc+c-b-1}{a} \right \rfloor$$

简单的化简之后就是这样 ：

$$n(m+1) - f(c,c-b-1,a,m)$$

我们发现，此时它可以继续递归了！
观察递归过程，像极了欧几里得算法 （这也是它被叫做类欧几里得算法的原因）:

int gcd(int a,int b) {return b ? gcd(b,a%b) : a;}

(因为 $a \ge c \ || \ b \ge c$ 时取模， $a < c \ \&\&\ b < c$ 时交换 )
那么递归边界也就是 $a = 0$ 的情况显然此时的柿子可以 $O(1)$ 求解
那么最基本的类欧几里得算法到这里可以说是结束了（很简单对不对）
所以下面我们当然还有扩展版 ：）

step 2 & 3 :

step 2 :

求一个柿子 ：

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

step 3 :

求另外一个柿子 ：

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

这两个柿子看起来就很友善对不对

求$a \ge c \ || \ b \ge c$ 时的情况都比较简单，虽然项数可能多一点但是推柿子的难度不大，所以这里直接放结果应该没太大问题（我觉得我上边写的挺详细的） ：
（中间用了一个小学奥数级别的结论： $\sum _{i = 1} ^ {n} i^2 = \frac{n(n+1)(2n+1)}{6} $ )
$a \ge c \ || \ b \ge c$ 时 ：

$$g(a,b,c,n)= g(a \text{ mod } c, b \text{ mod } c,c,n) + \left \lfloor \frac{a}{c} \right \rfloor\frac{n(n+1)(2n+1)}{6} + \left \lfloor \frac{b}{c} \right \rfloor \frac{n(n+1)}{2}$$ $$h(a,b,c,n) = h(a \text{ mod } c, b \text{ mod } c,c,n) + 2\left \lfloor \frac{b}{c} \right \rfloor f(a \text{ mod } c,b \text{ mod } c,c,n)$$ $$+ 2\left \lfloor \frac{a}{c} \right \rfloor g(a \text{ mod } c,b \text{ mod } c,c,n) + \left \lfloor \frac{a}{c} \right \rfloor ^ 2\frac{n(n+1)(2n+1)}{6} + \left \lfloor \frac{b}{c} \right \rfloor ^ 2 (n+1) + \left \lfloor \frac{a}{c} \right \rfloor \left \lfloor \frac{b}{c} \right \rfloor n(n+1)$$

(因为h的柿子稍微有点长所以换了个行不然就丑死了虽然换行之后也只能保证全屏情况下能看）
接下来就是 $a < c \ \&\&\ b < c$ 的部分了 ：
对于 $g$ :
我们设 $m = \left \lfloor \frac{an+b}{c} \right \rfloor -1$
那么就有：

$$g(a,b,c,n) = \sum_{i = 0}^{n} i \left \lfloor \frac{ai+b}{c} \right \rfloor$$ $$= \sum_{j = 0} ^ {m}\sum_{i = 0}^{n}\left [ j < \left \lfloor \frac{ai+b}{c} \right \rfloor \right ] \cdot i$$

与上文相同的化简方式可得 ：

$$\sum_{j = 0}^{m} \sum_{i=0}^{n} \left [ i > \left \lfloor \frac{jc+c-b-1}{a} \right \rfloor \right ] \cdot i$$

此时我们设 $t = \left \lfloor \frac{jc+c-b-1}{a} \right \rfloor$
显然只有当 $i \ge t + 1$ 时才产生贡献，方括号中值为 $1$ ，乘上 $i$ 之后显然是一个等差数列
则由小学二年级就学过的等差数列求和公式可得：

$$\sum_{j = 0}^{m}\frac{1}{2}(t+n+1)(n-t)$$

拆开之后合并同类项，可以化为：

$$\frac{1}{2} \left [ n(m+1)(n+1) - \sum_{j = 0}^{m} t^2 - \sum_{j = 0}^{m} t \right ]$$

然后我们欣喜地发现：可以递归力（乐）
也就是化成了这个柿子：

$$\frac{1}{2} \left[ n(m+1)(n+1) - h(c,c-b-1,a,m) - f(c,c-b-1,a,m) \right]$$

欸，但是这里边用到了 $h$ ，我们发现我们 $h$ 的柿子还没有推完
所以去补 $h$ 的坑 ：
对于$h$ ：
这里有一个不太好想到的变换 ：

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

这样做是为了把不好处理的平方拆成两部分，避免添加$j$的时候出现$\sum$相乘的形式
所以就得到了：

$$h(a,b,c,n) = \sum_{i = 0}^{n} \left \lfloor \frac{ai+b}{c} \right \rfloor ^2 = \sum_{i = 0}^{n} \left [ (2\sum_{j = 1}^{\left \lfloor \frac{ai+b}{c} \right \rfloor}j) - \left \lfloor \frac{ai+b}{c} \right \rfloor \right]$$ $$= (2\sum_{i = 0}^{n}\sum_{j = 1}^{\left \lfloor \frac{ai+b}{c} \right \rfloor }j) - f(a,b,c,n)$$

可以看到柿子的后半部分已经可以递归求解了，那么问题就在前半部分

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

（废话，把$j$换成$j+1$就行）
然后设一个和之前一样的 $m$ ,按照套路把条件扔下来，把枚举 $j$ 提到前面去，可得 ：

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

即 ：

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

然后设一个和之前一样的 $t$ ，（其实设这个只是为了好看和好敲公式，不设也是一样的）就可以得到 ：

$$\sum_{j = 0}^{m}(j+1)\sum_{i = 0}^{n} \left[ i > t \right ]$$

也就是 ：

$$\sum_{j = 0}^{m}(j+1)(n-t)$$ $$\frac{1}{2}n(m+1)(m+2) - \sum_{j = 0}^{m}(j+1)\left \lfloor \frac{jc+c-b-1}{a} \right \rfloor$$ $$\frac{1}{2} n(m+1)(m+2) - g(c,c-b-1,a,m) - f(c,c-b-1,a,m)$$

和原柿的后半部分合起来，也就是 ：

$$h(a,b,c,n) = n(m+1)(m+2) - 2g(c,c-b-1,a,m) - 2f(c,c-b-1,a,m) - f(a,b,c,n)$$

然后这是三个柿子之前就可以相互递归，全都求出来了
总结一下，三个柿子推完之后就是 ：

$$m = \left \lfloor \frac{an+b}{c} \right \rfloor - 1$$ $$f(a,c,b,n)= \begin{cases} a \ge c \ ||\ b\ge c : \\ \frac{n(n+1)}{2} \left \lfloor \frac{a}{c} \right \rfloor + (n+1) \left \lfloor \frac{b}{c} \right \rfloor + f(a\text{ mod }c,b\text{ mod }c,c,n)\\ a < c \ \&\&\ b < c : \\ n(m+1) - f(c,c-b-1,a,m) \end{cases}$$ $$g(a,c,b,n)= \begin{cases} a \ge c \ ||\ b\ge c : \\ g(a \text{ mod } c, b \text{ mod } c,c,n) + \left \lfloor \frac{a}{c} \right \rfloor\frac{n(n+1)(2n+1)}{6} + \left \lfloor \frac{b}{c} \right \rfloor \frac{n(n+1)}{2} \\ a < c \ \&\&\ b < c : \\ \frac{1}{2} \left[ n(m+1)(n+1) - h(c,c-b-1,a,m) - f(c,c-b-1,a,m) \right] \end{cases}$$ $$h(a,c,b,n)= \begin{cases} a \ge c \ ||\ b\ge c : \\ h(a \text{ mod } c, b \text{ mod } c,c,n) + 2\left \lfloor \frac{b}{c} \right \rfloor f(a \text{ mod } c,b \text{ mod } c,c,n) + 2\left \lfloor \frac{a}{c} \right \rfloor g(a \text{ mod } c,b \text{ mod } c,c,n) + \left \lfloor \frac{a}{c} \right \rfloor ^ 2\frac{n(n+1)(2n+1)}{6} + \left \lfloor \frac{b}{c} \right \rfloor ^ 2 (n+1) + \left \lfloor \frac{a}{c} \right \rfloor \left \lfloor \frac{b}{c} \right \rfloor n(n+1) \\ a < c \ \&\&\ b < c : \\ n(m+1)(m+2) - 2g(c,c-b-1,a,m) - 2f(c,c-b-1,a,m) - f(a,b,c,n) \end{cases}$$

最后是洛谷上类欧几里得算法的模板P5170
附上马蜂恶臭的代码 ：

#include<bits/stdc++.h>
namespace Pozhu{
using namespace std;
typedef long long ll;
int T;
const ll p = 998244353;
ll i2 = 499122177,i6 = 166374059;//i2 : %p 意义下2的逆元，i6同理

struct node{
    ll f,g,h;
    node(){f = g = h = 0;}
};

void work();
node doit(ll ,ll ,ll ,ll);

void main()
{
    scanf("%d",&T);
    while(T--) work();
    return;
}

node doit(ll n,ll a,ll b,ll c)
{
    node ass;
    ll ac = a / c,bc = b / c,n1 = n+1,n21 = n * 2 + 1;
    ll m = ((a * n + b) / c) - 1,m1 = m + 1,m2 = m + 2;
    if(a == 0)
    {//到达递归边界时，三个柿子的值都可以O(1)求出
        ass.f = n1 * bc % p;
        ass.g = n * bc % p * n1 % p * i2 % p;
        ass.h = bc * bc % p * n1 % p;
        return ass;
    }
    if(a >= c || b >= c)
    {
        ass.f = n * n1 % p * i2 % p * ac % p + n1 * bc % p;
        ass.g = ac * n % p * n1 % p * n21 % p * i6 % p 
            + bc * n % p * n1 % p * i2 % p;
        ass.h = ac * ac % p * n % p * n1 % p * n21 % p * i6 % p 
            + bc * bc % p * n1 % p + ac * bc % p * n % p * n1 % p;
        ass.f %= p,ass.g %= p,ass.h %= p;
        node nxt = doit(n, a % c, b % c, c);
        ass.h += nxt.h + 2 * bc % p * nxt.f % p + 2 * ac % p * nxt.g % p;
        ass.g += nxt.g;
        ass.f += nxt.f;
        ass.f = (ass.f % p + p) % p;
        ass.g = (ass.g % p + p) % p;
        ass.h = (ass.h % p + p) % p;
        return ass;
    }
    node nxt = doit(m, c,c - b - 1, a);
    ass.f = n * m1 % p - nxt.f;ass.f = (ass.f % p + p) % p;
    ass.g = n * n1 % p * m1 % p - nxt.h - nxt.f;ass.g = (ass.g % p * i2 % p + p) % p;
    ass.h = n * m1 % p * m2 % p - 2 * nxt.g % p - 2 * nxt.f % p - ass.f;ass.h = (ass.h % p + p) % p;
    return ass;
}

inline void work()
{
    ll n,a,b,c;
    scanf("%lld%lld%lld%lld",&n,&a,&b,&c);
    node ans = doit(n,a,b,c);
    printf("%lld %lld %lld\n",ans.f,ans.h,ans.g);//注意输出顺序
    return;
}

}

signed main()
{
    Pozhu :: main();
    return 0;
}

全文完
by Pozhu
2022.7.20