题目链接

Dead Fraction POJ - 1930

思路

$$ 无限循环小数化分数\\\\0.abcdefg如果efg循环\\\\abcdefg / 10000000 + efg / (999 * 10000000) $$

时间复杂度

$$ O(N) $$

代码

#include <iostream>
#include <string>

using namespace std;

long long gcd(long long a, long long b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

pair<long long , long long> work(string s, int k) {
    long long x1 = 0, y1 = 1, x2 = 0, y2 = 0, z = 1;
    for (int i = 0; i < (int)s.length(); i++) {
        x1 *= 10;
        x1 += s[i] - '0';
        y1 *= 10;
        if ((int)s.length() - i <= k) {
            x2 *= 10;
            x2 += s[i] - '0';
            y2 *= 10;
            y2 += 9;
        }
        z *= 10;
    }
    y2 *= z;
    long long d = gcd(x1, y1);
    x1 /= d;
    y1 /= d;

    d = gcd(x2, y2);
    x2 /= d;
    y2 /= d;

    d = gcd(y1, y2);
    x1 *= y2 / d;
    x2 *= y1 / d;
    x1 += x2;
    y1 /= d;
    y1 *= y2;

    d = gcd(x1, y1);
    x1 /= d;
    y1 /= d;
    return make_pair(x1, y1);
}

int main() {
    string s;
    while (cin >> s) {
        if (s == "0") {
            break;
        }
        string ss;
        for (int i = 2; i < (int)s.length(); i++) {
            if (s[i] == '.') {
                break;
            }
            ss += s[i];
        }
        long long x = -1, y = -1;
        for (int i = 0; i < (int)ss.length(); i++) {
            pair<long long, long long> w = work(ss, i + 1);
            if (y == -1 || w.second < y) {
                x = w.first;
                y = w.second;
            }
        }
        cout << x << "/" << y << endl;
    }
    return 0;
}