专栏文章

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

llinjunye
AT_abc408_g题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip4ocvm
此快照首次捕获于
2025/12/03 06:06
3 个月前
此快照最后确认于
2025/12/03 06:06
3 个月前
查看原文
其实这是一道原题，详情见 P5179。
首先看到这道题的第一眼，一般都是二分吧……那么我们来想一下：
它要求 qq，那么我们二分 pp，那么式子可以变成 q<BA×pq<\frac{B}{A}\times p 和 q>DC×pq>\frac{D}{C}\times p。因为 pp 是整数，所以我们能确定右边界为 ⌊BpA⌋\lfloor\frac{Bp}{A}\rfloor，左边界为 ⌈DpC⌉\lceil\frac{Dp}{C}\rceil，只要判断左边界不大于右边界即可。
但是，这是错的。你可以试试第一组数据下 pp 为 11 至 1010 的情况，你会惊喜的发现它不单调！
原因很简单，左边界为上取整，如果它正好比 xx 大一点点，那么左边界为 x+1x+1，这时候可能大于右边界。
那么怎么做呢？首先你需要发现如果要求 qq，那么 pp 也一定要求，然后你就要想怎么去求。
如果学过类欧的话，应该不难想到类欧的策略。如果不会也没关系，不影响我们的推导。
首先我们先考虑边界情况 p=q=1p=q=1。这个时候，AB<1\frac{A}{B}<1，CD>1\frac{C}{D}>1。不难得出 A<BA<B 且 C>DC>D 的时候是这样的。
然后我们就想通过多次变换，使得 A<BA<B 且 C>DC>D。
这里有一个很巧妙的思路：将我们的 AB\frac{A}{B} 和 CD\frac{C}{D} 全取倒数，那么限制条件就能变成 DC<qp<BA\frac{D}{C}<\frac{q}{p}<\frac{B}{A}。这时候如果 DC>1\frac{D}{C}>1，我们就统一减去 ⌊DC⌋\lfloor\frac{D}{C}\rfloor。这么一直做，我们就能得出正解啦！
为什么这个是对的呢？那么我们要证明当要求 qq 小的时候，pp 同时会变小（或要求 pp 小的时候，qq 同时会变小）。证明如下：
考虑反证法，假设我们让分母更小时，分子要变大。那么我们应当存在另一个符合条件的分数 xy\frac{x}{y}，满足 x>px>p 且 y<qy<q。那么 xy<py<pq\frac{x}{y}<\frac{p}{y}<\frac{p}{q}，显然 py\frac{p}{y} 更优（分子和分母均更小）。
或者我们让分子更小时，分母要变大。那么我们应当存在另一个符合条件的分数 xy\frac{x}{y}，满足 x<px<p 且 y>qy>q。那么 xy>xq>pq\frac{x}{y}>\frac{x}{q}>\frac{p}{q}，显然 xq\frac{x}{q} 更优（分母和分子均更小）。
这两个假设与结论均矛盾，所以我们让分母（或分子）变小时，分子（或分母）也会变小。证毕。
代码如下：
CPP
#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;
}
但是这样做复杂度真的优秀吗？你可以根据代码，这么感性理解：首先考虑 CC 和 DD 的变化，发现它们先被辗转相除（也就是代码中的 d%c,c），然后第二轮我们不管，然后第三轮再次被辗转相除了一下……这其实就是求最大公约数的思路！不难得出辗转相除法的复杂度为 O(log⁡n)O(\log n)，那么总复杂度也不会很高。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...