「Luogu 5179」Fraction

发表于 | | 阅读次数:
字数统计: 649 字

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$ 种情况考虑：

  1. $\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$ 即可。

  2. $a=0$

    这意味着只需要满足 $\frac{p}{q}<\frac{c}{d}​$，即为 $q>\frac{pd}{c}​$。我们为了取得最优解，可以直接取 $p=1,q=\left\lfloor\frac{d}{c}\right\rfloor+1​$。

  3. $a\le b$ 且 $c\le d$

    这意味着我们无法直接求解，需要进行一个转化：将原式 $\frac{a}{b}<\frac{p}{q}<\frac{c}{d}​$ 的每个分数都取倒数，由于每个数都是正数，那么可以得到 $\frac{d}{c}<\frac{q}{p}<\frac{b}{a}​$，直接递归处理即可。

  4. $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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
#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;
}
0%