类欧几里得算法|[BZOJ2712][[Violet 2]棒球][类欧几里得算法] 2017|数论|Bzoj

[BZOJ2712][[Violet 2]棒球][类欧几里得算法] 类似于下面这道题吧，只要把小数转换成分数就好了。
http://blog.csdn.net/g1n0st/article/details/62044709
代码：

#include using namespace std; typedef long long ll; typedef pair abcd; inline ll Min(const ll &a, const ll &b) { return a < b ? a : b; } 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 = p1 / q1 + 1; abcd ret(0,0); if (l * q2 < p2) return abcd(l, 1); if (p1 == 0) return abcd(1, 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, r; int n; while (~scanf("%d 0.%lld", &n, &r)) { if (r == 0) { printf("1\n"); continue; } ll x = 10; while (n--) x *= 10; p1 = r * 10 - 5, q1 = x, p2 = r * 10 + 5, q2 = x; 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\n", Min(ans.second, q1)); } return 0; }

完。
【类欧几里得算法|[BZOJ2712][[Violet 2]棒球][类欧几里得算法]】By g1n0st