BZOJ2187 fraction <类欧几里得>

Problem

fraction

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;259\;MB}$

Description

给出$4$个正整数$a,b,c,d$，求一个最简分数$\frac{p}{q}$满足$\frac{a}{b}<\frac{p}{q}<\frac{c}{d}$。
若有多组解，输出$q$最小的一组，若仍有多组解，输出$p$最小的一组。

Input

本题有多组数据，有若干行，每行$4$个数$a,b,c,d$。以文件的末尾作为结束。

Output

对于输入的每组数据输出一个最简分数$\frac{p}{q}$。

Sample Input

1 3 1 2
2 1 3 1
2 1 4 1
1000 1001 1001 1002

Sample Output

2/5
5/2
3/1
2001/2003

HINT

对于$100\%$的数据$1\le a,b,c,d\le10^9$,$1\le 数据组数\le 500$
数据保证至少存在一个最简分数符合条件。

标签：类欧几里得

Solution

类欧几里得基础题。

设$f(a,b,c,d)$为满足$\frac{a}{b}<\frac{p}{q}<\frac{c}{d}$的$p,q$，考虑将其转化为规模更小的问题。

• 若$\frac{a}{b}$和$\frac{c}{d}$间相差至少一个整数，则$p$为最小符合条件的整数，$q$为$1$
• 若$a\le b 且 c\le d$，则一定有等价不等式$\frac{b}{a}>\frac{q}{p}>\frac{d}{c}$，于是将问题转化为$f(d,c,b,a)$，求出$\frac{q}{p}$后颠倒分子分母得到$\frac{p}{q}$
• 若$a>b$或$c>d$，令$t=\lfloor\frac{a}{b}\rfloor$，则有$\frac{a-bt}{b}<\frac{p-qt}{q}<\frac{c-dt}{d}$，问题转化为$f(a-bt,b,c-dt,d)$，求出$\frac{p-qt}{q}$后即可还原出$\frac{p}{q}$

由于每次均将参数变为其辗转相模的结果，故而复杂度和欧几里得算法大致相同。

Code

#include <bits/stdc++.h>
using namespace std;
typedef double dnt;
typedef long long lnt;
lnt gcd(lnt x, lnt y) {return y ? gcd(y, x%y) : x;}
lnt flr(lnt x, lnt y) {return (lnt)floor((dnt)x/(dnt)y);}
lnt cel(lnt x, lnt y) {return (lnt)ceil((dnt)x/(dnt)y);}
void getans(lnt a, lnt b, lnt c, lnt d, lnt &p, lnt &q) {
    if (flr(a, b)+1 <= cel(c, d)-1) p = flr(a, b)+1, q = 1;
    else if (!a) p = 1, q = flr(d, c)+1;
    else if (a <= b && c <= d) getans(d, c, b, a, q, p);
    else {lnt k = a/b; getans(a-b*k, b, c-d*k, d, p, q), p += q*k;}
}
int main() {
    lnt a, b, c, d, p, q, t;
    while (~scanf("%lld%lld%lld%lld", &a, &b, &c, &d))
        t = gcd(a, b), a /= t, b /= t, 
        t = gcd(c, d), c /= t, d /= t, 
        getans(a, b, c, d, p, q), 
        printf("%lld/%lld\n", p, q);
    return 0;
}