专栏文章

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

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

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mip54n1m
此快照首次捕获于
2025/12/03 06:19
3 个月前
此快照最后确认于
2025/12/03 06:19
3 个月前
查看原文
题目跳楼机
双倍经验

正文开始

阅读理解

给出 AA，BB，CC，DD，求最小满足 AB<pq<CD\dfrac{A}{B}<\dfrac{p}{q}<\dfrac{C}{D} 的 qq。

思路

先从特殊情况入手，当 AB<1\dfrac{A}{B}<1 且 CD>1\dfrac{C}{D}>1 时，很明显，最小的 pq\dfrac{p}{q} 即为 11\dfrac{1}{1}。
那我们思路就很明确了，将 AB\dfrac{A}{B} 和 CD\dfrac{C}{D} 化成 AB<1\dfrac{A}{B}<1 且 CD>1\dfrac{C}{D}>1 的形式，再对 pp 与 qq 进行回溯。
怎么转化呢？我们可以循环以下步骤：
  • 当 AB<1\dfrac{A}{B}<1 且 CD<1\dfrac{C}{D}<1 时，将不等式 AB<CD\dfrac{A}{B}<\dfrac{C}{D} 变为 DC<BA\dfrac{D}{C}<\dfrac{B}{A}
  • 当 AB>1\dfrac{A}{B}>1 且 CD>1\dfrac{C}{D}>1 时，将不等式 AB<CD\dfrac{A}{B}<\dfrac{C}{D} 变为 A−⌊A/B⌋×BB<C−⌊A/B⌋×BD\dfrac{A-\lfloor A/B\rfloor\times B}{B}<\dfrac{C-\lfloor A/B\rfloor\times B}{D}
  • 当 AB<1\dfrac{A}{B}<1 且 CD>1\dfrac{C}{D}>1 时，将 pp 与 qq 赋值为 11，然后回溯。
注意：需要记录变化过程，建议使用递归。
回溯过程：
  • 当上一步是将不等式 AB<CD\dfrac{A}{B}<\dfrac{C}{D} 变为 DC<BA\dfrac{D}{C}<\dfrac{B}{A} 时，将 pq\dfrac{p}{q} 变为 qp\dfrac{q}{p}。
  • 当上一步是将不等式 AB<CD\dfrac{A}{B}<\dfrac{C}{D} 变为 A−⌊A/B⌋×BB<C−⌊A/B⌋×BD\dfrac{A-\lfloor A/B\rfloor\times B}{B}<\dfrac{C-\lfloor A/B\rfloor\times B}{D} 时将 pq\dfrac{p}{q} 变为 p+⌊A/B⌋×qq\dfrac{p+\lfloor A/B \rfloor\times q}{q}
最后再输出 qq 即可。

代码

CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
int p,q;
inline void dfs(int a,int b,int c,int d){
	int m=a/b;
	if(a>=b&&c>=d){
		dfs(a-m*b,b,c-m*d,d);
		p+=m*q;
	}
	else if(a<b&&c>d)p=q=1;
	else {
		dfs(d,c,b,a);
		swap(p,q);
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int T;cin>>T;
	while(T--){
		int A,B,C,D;
		cin>>A>>B>>C>>D;
		dfs(A,B,C,D);
		cout<<q<<'\n';
	}
	return 0;
}

评论

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

正在加载评论...