题解 P5179 【Fraction】

Siyuan · 2019-02-08 10:50:11 · 题解

\Large\texttt{My Blog}

Description

题目链接：Luogu 5179

给你四个正整数 a,b,c,d，求一个最简分数 \frac{p}{q} 满足 \frac{a}{b}<\frac{p}{q}<\frac{c}{d}。

若有多组解，输出 q 最小的一组，若仍有多组解，输出 p 最小的一组。数据保证至少存在一个最简分数符合条件。

本题 T 组数据。

数据范围：1\le T\le 500，1\le a,b,c,d\le 10^9

Solution

其实这个问题的本质是类欧几里德算法。我们分为如下 3 种情况考虑：

\left\lfloor\frac{a}{b}\right\rfloor+1\le\left\lceil\frac{c}{d}\right\rceil-1
这意味着 \left(\frac{a}{b},\frac{c}{d}\right) 之间存在一个整数，我们直接让 p=1,p=\left\lfloor\frac{a}{b}\right\rfloor+1 即可。
a=0
这意味着只需要满足 \frac{p}{q}<\frac{c}{d}，即为 q>\frac{pd}{c}。我们为了取得最优解，可以直接取 p=1,q=\left\lfloor\frac{d}{c}\right\rfloor+1。
a\le b$ 且 $c\le d
这意味着我们无法直接求解，需要进行一个转化：将原式 \frac{a}{b}<\frac{p}{q}<\frac{c}{d} 的每个分数都取倒数，由于每个数都是正数，那么可以得到 \frac{d}{c}<\frac{q}{p}<\frac{b}{a}，直接递归处理即可。
a\ge b
这意味着第 1 个分数和第 3 个分数的整数部分都大于 0。接下来要进行一个重要的转化：我们可以将每个分数减去 \left\lfloor\frac{a}{b}\right\rfloor，直接递归处理 \frac{a\bmod b}{b}<\frac{p}{q}-\left\lfloor\frac{a}{b}\right\rfloor<\frac{c}{d}-\left\lfloor\frac{a}{b}\right\rfloor 即可。注意递归处理完后，需要将 p 加上 q\times \left\lfloor\frac{a}{b}\right\rfloor。

这个过程中形式上极其类似于欧几里德算法，将 (a,b) 转化为 (a\bmod b,b) 正是其精髓所在。

Code

#include <cstdio>
typedef long long LL;

LL gcd(LL x,LL y) {
    return y?gcd(y,x%y):x;
}
void sim(LL &x,LL &y) {
    LL d=gcd(x,y); x/=d,y/=d;
}
void solve(LL a,LL b,LL c,LL d,LL &p,LL &q) {
    sim(a,b),sim(c,d);
    LL x=a/b+1,y=(c-1)/d;
    if(x<=y) p=x,q=1;
    else if(!a) p=1,q=d/c+1;
    else if(a<=b&&c<=d) solve(d,c,b,a,q,p);
    else solve(a%b,b,c-d*(a/b),d,p,q),p+=q*(a/b);
}
int main() {
    LL a,b,c,d,p,q;
    while(~scanf("%lld%lld%lld%lld",&a,&b,&c,&d)) {
        solve(a,b,c,d,p,q);
        printf("%lld/%lld\n",p,q);
    }
    return 0;
}