题意：给定x和p，求一个最小的b使得存在一个 并且
。
题解：由于 ， 那么
,
, 于是
，从而
。那么我们就是要求一个最小的b，这就可以通过辗转相除（出题人管这叫辗转相除）：
Let's consider we are solving problem for
.
Here are three cases:
. Let's subtract
from both numbers. Obviously, solution is same up to adding it back.
. then
is answer! Note, that it minimize both parts of fraction.
. Let's solve for
. This is the same problem (up to answer inverse), but now we need, to minimize numerator, not denominator. But this doesn't matter, because step 2 optimize both!
——PavelKunyavskiy’ s comment :https://codeforces.com/blog/entry/67091?#comment-512389
btw, 出题人提到这个算法来自于 Code Jam 2019 Round 2 - New Elements Part 2 ，上述的算法描述也是这么找的
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
pll find_best(pll l,pll r){
if(l.first>=l.second){
ll fl = l.first / l.second;
pll res = find_best({l.first - fl * l.second, l.second}, {r.first - fl * r.second, r.second});
res.first += res.second * fl;
return res;
}
if(r.first>r.second){
return {1, 1};
}
pll res = find_best({r.second, r.first}, {l.second, l.first});
return {res.second, res.first};
}
int main()
{
ios::sync_with_stdio(false);
int round;
cin >> round;
while (round--)
{
ll p, x;
cin >> p >> x;
auto res = find_best({p, x}, {p, (x - 1)});
ll b = res.first;
ll y = res.second;
cout << (b * x - p * y) << "/" << b << endl;
}
}
