题解：AT_abc408_g [ABC408G] A/B < p/q < C/D

· · 题解

这是一个类欧几里得算法的经典题。

Part.1 前置知识

欧几里得算法：

如果你要求 \gcd(x,y)（这里假设 x\ge y），容易发现 \gcd(x,y)=\gcd(y,x\bmod y)。

欧几里得证明出，如果不停地如此递归直至 y=0，则答案为 x 且时间复杂度为 \log_2~x+y 级别的。

简单证明一下，假设 x\ge2y，则一次递归以后的 x'+y' 不会高于 2y，一次递归后 x+y 缩小到了原来的 \frac{1}{2}。

否则，有 x'=y,y'=x-y，和为 x，那么这一次递归后和 为 x，最不利的情况下 x+y 缩小到了原来的 \frac{2}{3}。

其实类欧几里得算法的精髓就是锁定原函数中的两个参数 x,y，然后让 x,y 递归后变为 y,x\bmod y 即可证明时间复杂度正确。

Part.2 本题思路

首先，要求最小的 q，使得存在整数 p，使得 \frac{A}{B}<\frac{p}{q}<\frac{C}{D}。

如果此时 A<B 且 C>D，那么 p=q=1 即可满足要求。

否则我们可以弄一下倒数，那么限制条件变为 \frac{D}{C}<\frac{q}{p}<\frac{B}{A}，然后将这个式子同时减去 m=\lfloor \frac{D}{C}\rfloor。

原式变为 \frac{D\bmod C}{C}<\frac{q-mp}{p}<\frac{B-mA}{A}。

先将当前 p,q 翻转（求倒数），然后将它拿去递归，再翻回来，最后将 q 加上 mp 即可。

锁定 c,d 两个因数，会发现，一轮后，它先做了一次类似欧几里得的变化，然后被拿去当了 a,b，然后 b 减少了，又去当了 c,d，如此往复，易证时间复杂度为 O(\log_2(a+b+c+d)) 级别。

Part.3 代码

接下来上满级小清新代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
int p,q;
void solve(int a,int b,int c,int d){
    if (a<b&&c>d) p=1,q=1;
    else{
        swap(p,q);
        solve(d%c,c,b-(d/c)*a,a);
        swap(p,q);
        q+=(d/c)*p; 
    }
}
signed main(){
    int t; cin>>t;
    while (t--){
        int a,b,c,d; cin>>a>>b>>c>>d;
        solve(a,b,c,d);
        cout<<q<<"\n";
    }
}

Part.4 后记

其实类欧几里得算法是一个奇妙的技巧。

比赛时只有 200+ 个人写出来，说明这个算法并不是非常普及（毕竟数论变换都有 600+ 人会），而我赛时也不会。

我看赛时我的学伴们好多人都会，甚至有一个人排到了前十名，而我排名 505，痛掉 13 分，但是我赛后了解到了这个技巧并学习了它。

我想，排名和 rated 并不是最重要的，增长经验才是打比赛的真正目的吧。至此，我推荐大家多打打比赛，让自己在千锤百炼中顽强成长吧！