HDU-6624 （杭电多校第5场 fraction）辗转相除

题意：给定x和p，求一个最小的b使得存在一个 并且。

题解：由于 ， 那么 , , 于是 ，从而 。那么我们就是要求一个最小的b，这就可以通过辗转相除（出题人管这叫辗转相除）：

Let's consider we are solving problem for .

Here are three cases:

1. . Let's subtract from both numbers. Obviously, solution is same up to adding it back.

2. . then is answer! Note, that it minimize both parts of fraction.

3. . 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;
    }
}