专栏文章

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

TTimmylyx
AT_abc408_g题解参与者 4已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@mip5nr30
此快照首次捕获于
2025/12/03 06:34
3 个月前
此快照最后确认于
2025/12/03 06:34
3 个月前
查看原文
这是一个类欧几里得算法的经典题。

Part.1 前置知识

欧几里得算法：
如果你要求 gcd⁡(x,y)\gcd(x,y)（这里假设 x≥yx\ge y），容易发现 gcd⁡(x,y)=gcd⁡(y,x mod y)\gcd(x,y)=\gcd(y,x\bmod y)。
欧几里得证明出，如果不停地如此递归直至 y=0y=0，则答案为 xx 且时间复杂度为 log⁡2 x+y\log_2~x+y 级别的。
简单证明一下，假设 x≥2yx\ge2y，则一次递归以后的 x′+y′x'+y' 不会高于 2y2y，一次递归后 x+yx+y 缩小到了原来的 12\frac{1}{2}。
否则，有 x′=y,y′=x−yx'=y,y'=x-y，和为 xx，那么这一次递归后和 为 xx，最不利的情况下 x+yx+y 缩小到了原来的 23\frac{2}{3}。
其实类欧几里得算法的精髓就是锁定原函数中的两个参数 x,yx,y，然后让 x,yx,y 递归后变为 y,x mod yy,x\bmod y 即可证明时间复杂度正确。

Part.2 本题思路

首先，要求最小的 qq，使得存在整数 pp，使得 AB<pq<CD\frac{A}{B}<\frac{p}{q}<\frac{C}{D}。
如果此时 A<BA<B 且 C>DC>D，那么 p=q=1p=q=1 即可满足要求。
否则我们可以弄一下倒数，那么限制条件变为 DC<qp<BA\frac{D}{C}<\frac{q}{p}<\frac{B}{A}，然后将这个式子同时减去 m=⌊DC⌋m=\lfloor \frac{D}{C}\rfloor。
原式变为 D mod CC<q−mpp<B−mAA\frac{D\bmod C}{C}<\frac{q-mp}{p}<\frac{B-mA}{A}。
先将当前 p,qp,q 翻转（求倒数），然后将它拿去递归，再翻回来，最后将 qq 加上 mpmp 即可。
锁定 c,dc,d 两个因数，会发现，一轮后，它先做了一次类似欧几里得的变化，然后被拿去当了 a,ba,b，然后 bb 减少了，又去当了 c,dc,d，如此往复，易证时间复杂度为 O(log⁡2(a+b+c+d))O(\log_2(a+b+c+d)) 级别。

Part.3 代码

接下来上满级小清新代码：
CPP
#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+200+ 个人写出来，说明这个算法并不是非常普及（毕竟数论变换都有 600+600+ 人会），而我赛时也不会。
我看赛时我的学伴们好多人都会，甚至有一个人排到了前十名，而我排名 505，痛掉 13 分，但是我赛后了解到了这个技巧并学习了它。
我想，排名和 rated 并不是最重要的，增长经验才是打比赛的真正目的吧。至此，我推荐大家多打打比赛，让自己在千锤百炼中顽强成长吧！

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...