【3】题解：AT_abc408_g [ABC408G] A/B < p/q < C/D【数学】【类欧几里得】
ExFish
·
·
题解
怎么说，又是一道类欧？
只不过这个东西跟我们类欧的函数不太一样，考虑类欧的思想，进行辗转相除。
是这么一个东西，原式满足不等式：
\frac{a}{b}<\frac{p}{q}<\frac{c}{d}
取倒数：
\frac{d}{c}<\frac{q}{p}<\frac{b}{a}
分离常数，设 v=\lfloor \frac{d}{c} \rfloor ：
\frac{d-cv}{c}<\frac{q-vp}{p}<\frac{b-va}{a}
其实就是：
\frac{d\bmod c}{c}<\frac{q-vp}{p}<\frac{b-va}{a}
递归，我们发现：
$$
\frac{a}{b}<1<\frac{c}{d}
$$
那么取 $p=1,q=1$。
本质就是递归到这个状态。
然后我们可以考虑逆推，每一次都有调换。
最后输出答案 $q$ 即可。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
int T;
void gcd(int a,int b,int &p,int &q,int c,int d){
if(a<b&&c>d)
p=1,q=1;
else{
gcd(d%c,c,q,p,b-(d/c)*a,a);
q+=(d/c)*p;
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>T;
while(T--){
int a,b,c,d;
cin>>a>>b>>c>>d;
int p,q;
gcd(a,b,p,q,c,d);
cout<<q<<"\n";
}
}
```
代码跟上面一样，我就不过多赘述了。
但是求答案有必要讲一下，为什么要加回来呢？
我们倒推时其实不知道 $p$，$q$ 的值，只有倒推回来时才知道上一步的值，所以要加回 $vp$，才是原本 $q$ 的值。
综上，此题难度是小学数学题。
---
感谢管理提醒！
但是我们发现题目还给了一个限制：**要让 $q$ 最小。**
由于逆推的原因，我们发现我们已经满足了 $p$ 最小。
我们考虑证明 $p$ 最小时 $q$ 最小。
证明：
设已经求出的最小解为 $\frac{p}{q}$。
我们知道当 $q>1$ 可满足：$\frac{p}{q}<\frac{p}{q-1}<\frac{p+1}{q-1}$。
若 $\frac{p+1}{q-1}$ 且 $q>1$ 符合原式，那么存在一个解为 $\frac{p}{q-1}$，那么不满足 $\frac{p}{q}$ 为最小解。
我们注意到前提条件 $q>1$，但是 $q=1$ 时满足已经最小了。
所以我们发现当 $q$ 最小了，那么 $p$ 就最小。
同理可得 $p$ 最小时 $q$ 最小，综上 $p$ 最小时 $q$ 最小。