Bzoj|[BZOJ2187][fraction][类欧几里得算法] 2017|类欧几里得算法|数论

[BZOJ2187][fraction][类欧几里得算法] 题目大意: 求一个最简分数 p / q满足 a / b < p / q < c / d
若有多组解，输出q最小的一组，若仍有多组解，输出p最小的一组。
思路: $Bzoj|[BZOJ2187][fraction][类欧几里得算法]$
文章图片

代码：

#include using namespace std; typedef long long ll; typedef pair abcd; inline ll gcd(const ll &a, const ll &b) { if (!b) return a; return gcd(b, a % b); } inline abcd solve(ll p1, ll q1, ll p2, ll q2) { ll l = (ll)floor((double)p1 / q1) + 1, r = (ll)ceil((double)p2 / q2) - 1; abcd ret(0,0); if (l <= r) return abcd(l, 1); if (p1 == 0) return abcd(1, (ll)floor((double)q2 / p2) + 1); if (p1 <= q1 && p2 <= q2) { ret = solve(q2, p2, q1, p1); return abcd(ret.second, ret.first); } ll t = p1 / q1; ret = solve(p1 - q1 * t, q1, p2 - q2 * t, q2); ret.first += ret.second * t; return ret; } int main(void) { //freopen("in.txt", "r", stdin); ll p1, q1, p2, q2; while (~scanf("%lld%lld%lld%lld", &p1, &q1, &p2, &q2)) { ll g = gcd(p1, q1); p1 /= g, q1 /= g; g = gcd(p2, q2); p2 /= g, q2 /= g; abcd ans = solve(p1, q1, p2, q2); printf("%lld/%lld\n", ans.first, ans.second); } return 0; }

完。
【Bzoj|[BZOJ2187][fraction][类欧几里得算法]】By g1n0st