「Luogu 5179」Fraction

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%