51Nod - 1187 寻找分数_a/b<p/q<c/d_bphm的博客-程序员宝宝

在这里插入图片描述
这题其实不难，分类讨论即可：
(1)当a为0时，则必然p!=0，那么只要在这个条件下满足p/q < c/d即可，那么我们可以取p=1，此时有，1/q < c/d 即，d/c < q 为了q能够取等号，则有d/c+1 <= q（在整数运算下显然成立），即q取d/c+1，此时必然满足要求。
(2)当a>b时，可知a/b为假分数形式，那么可以将a/b（分数形式）拆分成a/b+(a%b)/b，
例如：5/3可以拆分成：1+2/3的形式。
那么实际可以将原式化成：a/b+(a%b)/b<a/b+p/q<a/b+c/d
即在某个全为真分数的式子中加上了a/b后变成了现在的式子即x/y<P/Q<i/j的形式。
故只要在(a%b)<p/q<c/d下求得p/q就可以求得现在P/Q了。
(3)当c>d，显然可以取p=1,q=1
(4)如果不符合上述任何一种情况的话，那么我们只需要对原来式子取倒数，即d/c<q/p<b/a，强行使它符合上述3种情况的任意一种，那么在这种情况下求得的p/q显然为原来的倒数，所以交换一下p,q即可

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<algorithm>
#include<sstream>
#include<bitset>
#define scand(a) scanf("%d",&a)
#define scandd(a,b) scanf("%d%d",&a,&b)
#define scanddd(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define mst(a,b) memset(a,b,sizeof(a))
#define lowbit(x) x&-x
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int maxn=2e5+5;
const ll mod=1e9+9;
ll p,q;
void likegcd(ll x,ll y,ll i,ll j)
{
    
	if(x==0)
	{
    
		p=1;
		q=j/i+1;
	}
	else if(x>=y)
	{
    
		/*
		显然现在的i/j是由x/y+c/d组成的，
		易知j==d，则要求得c可以从i/j-(x/y)*j/j取得c=i-(x/y)*j
		*/
		likegcd(x%y,y,i-(x/y)*j,j);
		p+=q*(x/y);
	}
	else if(i>j)
	{
    
		p=q=1;
	}
	else
	{
    
		likegcd(j,i,y,x);
		swap(p,q);
	}
}
int main()
{
    
	#ifdef local
	freopen("1.txt","r",stdin);
	#endif
	int T;
	scand(T);
	while(T--)
	{
    
		ll a,b,c,d;
		scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
		likegcd(a,b,c,d);
		printf("%lld/%lld\n",p,q);
	}
}

本文链接：https://blog.csdn.net/qq_43469254/article/details/104810438

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

Table of Contents - C++ 标准头文件列表 - VS6 - English - From MSDN - HackerJLY_HackerJLY的博客-程序员宝宝

AOSP 预编译_obj和obj_arm_github_33381613的博客-程序员宝宝

Android.bp 支持的预编译var prebuiltTypes = map[string]string{ "SHARED_LIBRARIES": "cc_prebuilt_library_shared", "STATIC_LIBRARIES": "cc_prebuilt_library_static", "EXECUTABLES": "cc_prebuilt_binary", "JAVA_LIBRARIES": "java

侧边下拉菜单_下拉菜单侧边_黎明lk的博客-程序员宝宝

侧边下拉菜单看到一个博客写下拉菜单，感觉很流畅，就模仿的写了一下js代码纯手敲<!DOCTYPE html><html> <head> <meta charset="UTF-8"> <title></title> <style type="text/css"> *{ margin: 0; padding: 0; } body,html{ height: 100%

Electron 基础学习第二天_openr.postmessage_FuyuumiAI的博客-程序员宝宝

Electron 基础学习（2）右键菜单创建contextMenu.js，代码如下const { remote } = require('electron')// 右键菜单模板// 配置参数与顶部菜单一致const menuList = [ { label: '复制', accelerator: 'ctrl+c' }, { label: '复制', accelerator: 'ctrl+v'

线上分享会预告|翻译质量控制实施方法_大辞科技的博客-程序员宝宝

质量在业内被认为是翻译的生命线，却也是翻译的一大痛点。大家一致认同保证质量这一观点，但是真正做到保证质量这四个字，难度却是非常大的。译创语言服务和大辞科技将联合举办一期线上分享会，围绕翻译质量话题展开分享，希望能够和大家一起讨论、交流。线上分享会预告|翻译质量控制实施方法...

【VUE实战】学习笔记（一）_vue 实战学习笔记_天空之蓝钻的博客-程序员宝宝

1. 前言：插值与表达式。生命周期。2. 生命周期：created 实例创建完成后调用，此阶段完成了数据的观测等，但尚未挂载， $el 还不可用。需要初始化处理一些数据时会比较有用，后面章节将有介绍．mounted el 挂载到实例上后调用，一般我们的第一个业务逻辑会在这里开始beforeDestroy 实例销毁之前调用。主要解绑一些使用 addEventListener 监听...