【BZOJ2187】fraction（类欧几里得算法）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【BZOJ2187】fraction（类欧几里得算法），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1407字，纯文字阅读大概需要3分钟。

内容图文

点此看题面

大致题意： 给定两个分数\(\frac ab\)和\(\frac cd\)，求\(\frac pq\)满足\(\frac ab<\frac pq<\frac cd\)，且在\(q\)尽量小的前提下\(p\)尽量小。

前言

这是怎么想到类欧几里得算法的。。。

我这种蒟蒻只会第一种情况，第二种情况都没想到。

类欧几里得算法

• 当\(\frac ab\)和\(\frac cd\)之间存在整数时，必然选择其中最小的整数。
• 当\(a=0\)时，条件就只有\(\frac pq<\frac cd\)，也就是\(q>\frac{dp}c\)。显然\(p=1\)时\(q\)可以取到最小值，此时\(q=\lfloor\frac dc\rfloor+1\)。
• 当\(a<b\)时，我们对所有数取倒数，得到\(\frac dc<\frac qp<\frac ba\)，递归做即可。
• 当\(a\ge b\)时，我们只保留\(\frac ab\)的小数部分，令\(t=\lfloor\frac ab\rfloor\)，得到\(\frac{a\%b}b<\frac{p-qt}q<\frac{c-dt}d\)，同样递归做即可。

于是这道题就做完了，理解起来其实并不难，但也太难想到了。

代码

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define swap(x,y) (x^=y^=x^=y)
using namespace std;
int a,b,c,d;
I void Get(CI a,CI b,CI c,CI d,int& x,int& y)//类欧几里得算法
{
	if(a/b+1<=(c-1)/d) return (void)(x=a/b+1,y=1);if(!a) return (void)(x=1,y=d/c+1);//存在整数；a=0
	a<b?(Get(d,c,b,a,x,y),swap(x,y)):(Get(a%b,b,c-(a/b)*d,d,x,y),x+=y*(a/b));//a<b；a≥b（注意修改得到正确的x,y）
}
int main()
{
	RI x,y;W(scanf("%d%d%d%d",&a,&b,&c,&d)==4) Get(a,b,c,d,x,y),printf("%d/%d\n",x,y);
	return 0;
}

内容总结

以上是互联网集市为您收集整理的【BZOJ2187】fraction（类欧几里得算法）全部内容，希望文章能够帮你解决【BZOJ2187】fraction（类欧几里得算法）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---