AT_abc408_g [ABC408G] A/B < p/q < C/D 题解

· · 题解

其实这是一道原题，详情见 P5179。

首先看到这道题的第一眼，一般都是二分吧……那么我们来想一下：

它要求 q，那么我们二分 p，那么式子可以变成 q<\frac{B}{A}\times p 和 q>\frac{D}{C}\times p。因为 p 是整数，所以我们能确定右边界为 \lfloor\frac{Bp}{A}\rfloor，左边界为 \lceil\frac{Dp}{C}\rceil，只要判断左边界不大于右边界即可。

但是，这是错的。你可以试试第一组数据下 p 为 1 至 10 的情况，你会惊喜的发现它不单调！

原因很简单，左边界为上取整，如果它正好比 x 大一点点，那么左边界为 x+1，这时候可能大于右边界。

那么怎么做呢？首先你需要发现如果要求 q，那么 p 也一定要求，然后你就要想怎么去求。

如果学过类欧的话，应该不难想到类欧的策略。如果不会也没关系，不影响我们的推导。

首先我们先考虑边界情况 p=q=1。这个时候，\frac{A}{B}<1，\frac{C}{D}>1。不难得出 A<B 且 C>D 的时候是这样的。

然后我们就想通过多次变换，使得 A<B 且 C>D。

这里有一个很巧妙的思路：将我们的 \frac{A}{B} 和 \frac{C}{D} 全取倒数，那么限制条件就能变成 \frac{D}{C}<\frac{q}{p}<\frac{B}{A}。这时候如果 \frac{D}{C}>1，我们就统一减去 \lfloor\frac{D}{C}\rfloor。这么一直做，我们就能得出正解啦！

为什么这个是对的呢？那么我们要证明当要求 q 小的时候，p 同时会变小（或要求 p 小的时候，q 同时会变小）。证明如下：

考虑反证法，假设我们让分母更小时，分子要变大。那么我们应当存在另一个符合条件的分数 \frac{x}{y}，满足 x>p 且 y<q。那么 \frac{x}{y}<\frac{p}{y}<\frac{p}{q}，显然 \frac{p}{y} 更优（分子和分母均更小）。

或者我们让分子更小时，分母要变大。那么我们应当存在另一个符合条件的分数 \frac{x}{y}，满足 x<p 且 y>q。那么 \frac{x}{y}>\frac{x}{q}>\frac{p}{q}，显然 \frac{x}{q} 更优（分母和分子均更小）。

这两个假设与结论均矛盾，所以我们让分母（或分子）变小时，分子（或分母）也会变小。证毕。

代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
void cal(int a,int b,int c,int d,int &A,int &B){
    if(a<b&&c>d){
        A=B=1;
        return;
    }
    cal(d%c,c,b-(d/c)*a,a,B,A);// d-(d/c)*c=d%c
    B+=(d/c)*A;
    return;
}
int a,b,c,d,A,B;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T=1;
    cin>>T;
    while(T--){
        cin>>a>>b>>c>>d;
        A=B=0;
        cal(a,b,c,d,A,B);
        cout<<B<<"\n";
    }
    return 0;
}

但是这样做复杂度真的优秀吗？你可以根据代码，这么感性理解：首先考虑 C 和 D 的变化，发现它们先被辗转相除（也就是代码中的 d%c,c），然后第二轮我们不管，然后第三轮再次被辗转相除了一下……这其实就是求最大公约数的思路！不难得出辗转相除法的复杂度为 O(\log n)，那么总复杂度也不会很高。