POJ 1930: Dead Fraction

概要

小数が与えられる．循環小数と見たとき，分母が最も小さくなる分数表示を求める．

解法

循環する区間を仮定して分数に直すという操作を繰り返す．
n桁の循環する小数は，cを循環する部分を表す整数とすると，c/(10^n-1)で得られる．

typedef unsigned long long ull;

ull gcd(ull x, ull y){
    return y ? gcd(y, x%y): x;
}

string s;
int main(){
    for(;;){
        cin >> s;
        if(s == "0") return 0;
        s = s.substr(2, s.size()-5);
        ull p, q, v, w, g;
        p = q = ULLONG_MAX;
        v = 1; w = 1;
        for(int i = 0; i < s.size(); ++i) w *= 10;
        for(int i = 0; i < s.size(); ++i){
            ull a, b, c, d;
            if(i == 0) a = 0;
            else       sscanf(s.substr(0, i).c_str(), "%llu", &a);
            b = v;
            sscanf(s.substr(i).c_str(), "%llu", &c);
            d = w - 1;

            g = gcd(a, b);
            a /= g; b /= g;
            g = gcd(c, d);
            c /= g; d /= g;
            g = gcd(c, v);
            c /= g;
            d *= v / g;

            g = gcd(b, d);
            a = a * (d / g) + c * (b / g);
            b = b / g * d;
            g = gcd(a, b);
            a /= g; b /= g;
            // cerr << ">" << a << "/" << b << endl;
            if(b < q){
                p = a; q = b;
            }

            v *= 10;
            w /= 10;
        }
        cout << p << "/" << q << endl;
    }
}