P5179 Fraction

Mars_Dingdang · 2021-04-04 10:42:30 · 题解

本题乍一看很简单：这不就是小学数学题吗……再一看发现不会做了。不过其实分好类，解法就明朗了。

题目大意

给你四个正整数 a,b,c,d，求一个最简分数 \dfrac p q 满足 \dfrac a b <\dfrac p q <\dfrac c d，且 q 尽可能小，在此基础上 p 尽可能小。

多组数据，数据范围：a,b,c,d\le 10^9。

大体思路

用 \omega 表示值域，\omega 与 10^9 同阶。

首先有许多种 O(T\log^2 \omega) 的做法。比如本题编号是 5179，而前几道题就有类欧几里得的模板 P5170，因而顺理成章的想到类欧几里得，套上二分即可。

这里介绍一种 \Theta(T\log \omega) 的算法。对 \dfrac a b,\dfrac c d 进行分类。首先对 \dfrac a b,\dfrac c d 利用欧几里得算法约分。

inline ll gcd(ll a,ll b){//求最大公因数
    if(!b) return a;
    return gcd(b,a%b);
}
inline void Div(ll &a,ll &b){//约分
    ll g=gcd(a,b);
    a/=g;
    b/=g;
}
inline void work(ll a,ll b,ll c,ll d,ll &p,ll &q){
    Div(a,b);Div(c,d);//未完待续

最基本的：若 \left\lfloor\dfrac a b\right\rfloor +1\le \left\lceil\dfrac c d\right\rceil-1，即这两个分数之间存在整数。由于题目要求正整数 q 尽可能小，因此 \dfrac p q 为整数，即 q=1 时必然满足。因此 p\leftarrow \left\lfloor\dfrac a b\right\rfloor +1,q\leftarrow 1。

    ll x=(a/b)+1,y=(c-1)/d;
    if(x<=y) p=x,q=1;

若 a=0，只需满足 \dfrac p q<\dfrac c d，由于均为正整数，移项可得 q>\dfrac{pd}c。由整数的离散性，q\ge \left\lfloor\dfrac {pd}c\right\rfloor+1，因此当 p=1 时，q 取最小值。

else if(a==0) p=1,q=(d/c)+1;

若 \dfrac a b,\dfrac c d 均为真分数，即 a<b\ and\ c<d，则无法直接求出。由于均为正整数，取倒数将式子变换得到 \dfrac d c<\dfrac q p<\dfrac b a，此时三个分数均为假分数（即分子比分母大），可通过递归求解。处理带分数的方法在 4 中将会介绍。

else if(a<=b && c<=d) work(d,c,b,a,q,p);
//取倒数

若 a\ge b，由于 \dfrac a b<\dfrac c d，此时三个分数均为带分数。令三个分数均减去 \left\lfloor\dfrac a b\right\rfloor，可以得到： \dfrac{a}b-\left\lfloor\dfrac a b\right\rfloor<\dfrac p q-\left\lfloor\dfrac a b\right\rfloor<\dfrac c d-\left\lfloor\dfrac a b\right\rfloor \therefore\dfrac{a\bmod b}b<\dfrac p q-\left\lfloor\dfrac a b\right\rfloor<\dfrac{c-d\times \left\lfloor\dfrac a b\right\rfloor}d

在递归时，不需要处理中间项 \dfrac p q-\left\lfloor\dfrac a b\right\rfloor，求出 p,q 后，令 p\leftarrow p+q\times \left\lfloor\dfrac a b\right\rfloor 即可。

else work(a%b,b,c-(d*(a/b)),d,p,q), //减去 a/b
    p+=(q*(a/b)); //处理 p

这样就可以在 \Theta(T\log \omega) 的复杂度下求解。但该算法本质仍是 O(T\log^2 \omega)，因为 \gcd 函数的复杂度是 O(\log \max(a,b))，即 O(\log \omega)，而递归求解时的 a\bmod b 共有 \log \max(a,b) 层，因此总复杂度仍为 O(T\log^2 \omega)，但实际效率优于此。

完整代码

#include<bits/stdc++.h>
using namespace std;
#define rep(ii,aa,bb) for(re int ii = aa; ii <= bb; ii++)
#define Rep(ii,aa,bb) for(re int ii = aa; ii >= bb; ii--)
typedef long long ll;
typedef unsigned long long ull;
//const int maxn = ;
namespace IO_ReadWrite {
    #define re register
    #define gg (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<21, stdin), p1 == p2) ? EOF :*p1++)
    char buf[1<<21], *p1 = buf, *p2 = buf;
    template <typename T>
    inline void read(T &x){
        x = 0; re T f=1; re char c = gg;
        while(c > 57 || c < 48){if(c == '-') f = -1;c = gg;}
        while(c >= 48 &&c <= 57){x = (x<<1) + (x<<3) + (c^48);c = gg;}
        x *= f;return;
    }
    inline void ReadChar(char &c){
        c = gg;
        while(!isalpha(c)) c = gg;
    }
    template <typename T>
    inline void write(T x){
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x/10);
        putchar('0' + x % 10);
    }
    template <typename T>
    inline void writeln(T x){write(x); putchar('\n');}
}
using namespace IO_ReadWrite;
inline ll gcd(ll a,ll b){
    if(!b) return a;
    return gcd(b,a%b);
}//最大公因数
inline void Div(ll &a,ll &b){
    ll g=gcd(a,b);
    a/=g;
    b/=g;
}//约分
inline void work(ll a,ll b,ll c,ll d,ll &p,ll &q){
    Div(a,b);Div(c,d);
    ll x=(a/b)+1,y=(c-1)/d;
    //分类
    if(x<=y) p=x,q=1;
    else if(a==0) p=1,q=(d/c)+1;
    else if(a<=b && c<=d) work(d,c,b,a,q,p);
    else work(a%b,b,c-(d*(a/b)),d,p,q), p+=(q*(a/b));
}//递归求解
ll a,b,c,d,p,q;
int main(){
    while(~scanf("%lld%lld%lld%lld",&a,&b,&c,&d)){//多组数据
        work(a,b,c,d,p,q);
        printf("%lld/%lld\n",p,q);
    }
    return 0;
}

后记

这道题如果没有 p,q 最优的限制就是一道红题，直接通分即可（最多像 NOIp 那样卡个高精）。
这题的题解写起来比代码还烦，\rm{\LaTeX} 极其恶心。