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

题意：给定x和p，求一个最小的b使得存在一个 $a<b$ 并且 $a \equiv b x(\bmod p)$ 。

题解：由于 $a \equiv b x(\bmod p)$ ，那么 $\exists y>0$ , $bx-a=py$ , 于是 $0<a=bx-py<b$ ，从而 $\frac{p}{x}<\frac{b}{y}<\frac{p}{x-1}$ 。那么我们就是要求一个最小的b，这就可以通过辗转相除（出题人管这叫辗转相除）：

Let's consider we are solving problem for $\left[\frac{p_{1}}{q_{1}}, \frac{p_{2}}{q_{2}}\right]$ .

Here are three cases:

$\frac{p_{1}}{q_{1}} \geq 1$ . Let's subtract $\left\lfloor\frac{p_{1}}{q_{1}}\right\rfloor$ from both numbers. Obviously, solution is same up to adding it back.

$\frac{p_{1}}{q_{1}}<1<\frac{p_{2}}{q_{2}}$ . then $1/1$ is answer! Note, that it minimize both parts of fraction.

$\frac{p_{2}}{q_{2}} \leq 1$ . Let's solve for $\left[\frac{q_{2}}{p_{2}}, \frac{q_{1}}{p_{1}}\right]$ . 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;
    }
}

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

推荐阅读更多精彩内容