可能是一道小学数学题

P5179 Fraction

给你 \(a,b,c,d\)，求一个最简分数 \(\dfrac pq\) 满足

\[\frac ab<\frac pq<\frac cd \]

若有多组解，输出 \(q\) 最小的，若仍有多个输出 \(p\) 最小的。以p/q格式输出。

首先我们证明一下答案一定满足 \(p\) 和 \(q\) 都最小，也就是不存在 \(\dfrac xy\)，使得 \(x>p,y<q\) 或 \(x<p,y>q\)。

若 \(x>p,y<q\)，则 \(\dfrac pq<\dfrac py<\dfrac xy\)，答案显然应为 \(\dfrac py\)。同理可得另一边。

然后开始分讨。

1.\(\left\lfloor\dfrac ab\right\rfloor+1\le\left\lceil\dfrac cd\right\rceil\)

那答案显然就是 \(p=\left\lfloor\dfrac ab\right\rfloor+1,q=1\)。

2. \(a=0\)

这时候 \(\dfrac pq<\dfrac cd\)，即 \(q>\dfrac{pd}c\)。取 \(p=1,q=\left\lfloor\dfrac dc\right\rfloor+1\)即可。

3. \(a\ge b\)

这时候可以三个数都减一个 \(\left\lfloor\dfrac ab\right\rfloor\)。

4. \(a<b,c<d\)

这里有点操作。这时候有 \(\dfrac dc<\dfrac qp<\dfrac ba\)。递归向下。

复杂度是对数级别的（至于对数了个什么玩意我也不知道）。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define int long long
using namespace std;
int a,b,c,d,p,q;
int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}
void solve(int a,int b,int c,int d,int &p,int &q){
    int g=gcd(a,b);a/=g;b/=g;
    g=gcd(c,d);c/=g;d/=g;
    int ret=a/b+1,tmp=ceil(1.0*c/d)-1;
    if(ret<=tmp){
        p=ret;q=1;return;
    }
    if(!a){
        p=1;q=d/c+1;return;
    }
    if(a>=b){
        solve(a%b,b,c-a/b*d,d,p,q);
        p+=a/b*q;
        return;
    }
    solve(d,c,b,a,q,p);
}
signed main(){
    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;
}