类欧几里得

类欧几里得只是复杂度同欧几里得相似，跟欧几里得没有关系。

引入 51Nod 1187

给出 $a,b,c,d$, 找一个分数$p/q$，使得$a/b < p/q < c/d$，并且$q$最小。例如：$1/3$同$1/2$之间，符合条件且分母最小的分数是$2/5$。（如果$q$相同，输出$p$最小的）$(1 \le a,b,c,d \le 10^9)$

下面进行分类讨论

1. 当$a=0$（递归边界1）

   由于$q>p\frac{d}{c}$，显然有$p=1,q=d/c+1$

2. 当$a\ge b$

   可以对不等式两边同时减去$\lfloor\frac{a}{b}\rfloor$，转化为情况$1/3/4$

3. 当$a<b,c>d$（递归边界2）

   显然有$p=1,q=1$

4. 其他情况

   对不等式两边求倒数，得$\frac{d}{c}<\frac{q}{p}<\frac{b}{a}$，且$d\ge c$，转化为情况$2$

AC代码

看了上面的例题，聪明的你一定会了吧？不妨来做一下下面这道例题。

例题 洛谷P5170 (opens new window)

给定 $n, a, b, c,$ 分别求 $\sum_{i=0}^{n}\left\lfloor\frac{a i+b}{c}\right\rfloor, \sum_{i=0}^{n}\left\lfloor\frac{a i+b}{c}\right\rfloor^{2}, \sum_{i=0}^{n} i\left\lfloor\frac{a i+b}{c}\right\rfloor$ 答案对 998244353 取模。

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

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

1.1 当$a\ge c$或$b\ge c$

$$\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{(a\%c)i+b\%c}{c}\right\rfloor+\frac{n(n+1)}{2}\lfloor\frac{a}{c}\rfloor+(n+1)\lfloor\frac{b}{c}\rfloor\\&=f(a\%c,b\%c,c,n)+\frac{n(n+1)}{2}\lfloor\frac{a}{c}\rfloor+(n+1)\lfloor\frac{b}{c}\rfloor\end{aligned}$$

转化为$a<c,b<c$的情况

1.2 当$a<c,b<c$

$$\begin{aligned}f(a,b,c,n)&=\sum_{i=0}^{n}\left\lfloor\frac{a i+b}{c}\right\rfloor\\&=\sum_{i=0}^{n}\sum_{j=1}^{\lfloor\frac{a i+b}{c}\rfloor}1\\&=\sum_{j=1}^{\lfloor\frac{an+b}{c}\rfloor}\sum_{i=0}^{n}\left[j\le\lfloor\frac{ai+b}{c}\rfloor\right]\end{aligned}$$

式$(2)$中的方括号为艾佛森括号，当条件成立时值为$1$，否则为$0$.

对不等式进行变换

$$j\le\lfloor\frac{ai+b}{c}\rfloor\leftrightarrow j\le\frac{ai+b}{c}\leftrightarrow jc\le ai+b\leftrightarrow jc-b-1<ai$$

再次下取整

$$\frac{jc-b-1}{a}<i \leftrightarrow\left\lfloor\frac{jc-b-1}{a}\right\rfloor<i$$

继续对原式进行化简

$$\begin{aligned}f(a,b,c,n) & = \sum_{j=1}^{\lfloor\frac{an+b}{c}\rfloor}\sum_{i=0}^{n}\left[i>\left\lfloor\frac{jc-b-1}{a}\right\rfloor\right]\\&=\sum_{j=1}^{\lfloor\frac{an+b}{c}\rfloor}\left(n-\left\lfloor\frac{jc-b-1}{a}\right\rfloor\right)\\&=n\left\lfloor\frac{an+b}{c}\right\rfloor-\sum_{j=1}^{\lfloor\frac{an+b}{c}\rfloor}\left\lfloor\frac{jc-b-1}{a}\right\rfloor\\&=n\left\lfloor\frac{an+b}{c}\right\rfloor-\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\left\lfloor\frac{jc+c-b-1}{a}\right\rfloor\\&=n\left\lfloor\frac{an+b}{c}\right\rfloor-f(c,c-b-1,a,\left\lfloor\frac{an+b}{c}\right\rfloor-1)\end{aligned}$$

上面的公式巨长，巨难写

式$(1)$到式$(2)$的转换：核心是通过限制转移，使得$j$不受$i$限制。

式$(3)$到式$(4)$的转换：$\sum\limits_{i=0}^{n}\left[i>\left\lfloor\frac{jc-b-1}{a}\right\rfloor\right]$实质上是统计大于$\left\lfloor\frac{jc-b-1}{a}\right\rfloor$的$i$的个数，可以改写作$n-\left\lfloor\frac{jc-b-1}{a}\right\rfloor$

使用式$(5)$进行递归求解，当$a=0$时，$f(a,b,c,n)=(n+1)\left\lfloor\frac{b}{c}\right\rfloor$

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

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

万能欧几里得

AC代码

51Nod 1187

#include <bits/stdc++.h>
#define Android ios::sync_with_stdio(false), cin.tie(NULL)

using namespace std;

void calc(int a, int b, int c, int d, int & p, int & q){
    if(a == 0){
        p = 1, q = d / c + 1;
    } else if(a >= b){
        int delta = a / b;
        calc(a%b, b, c - d*delta, d, p, q);
        p += q * delta;
    }else if(c > d){
        p = q = 1;
    }else{
        calc(d, c, b, a, q, p);
    }
}

void solve(){
    int a, b, c, d, p, q, g;
    cin >> a >> b >> c >> d;
    calc(a, b, c, d, p, q);
    g = __gcd(p, q);
    cout << p / g << "/" << q / g << "\n";
}

signed main(){
    Android;
    int t; cin >> t;
    while(t--) solve();
}