POJ 1930 - Dead Fraction（数学）

题目：

http://poj.org/problem?id=1930

题目：

将无限循环小数转化成分数，但是循环节不确定，要求出分母最小的那个分数。

思路：

百度知道了 无限循环小数转化成分数的方法。详见笔记=。=

CODE:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;
typedef long long ll;
char s[10];

ll gcd(ll a, ll b)
{
    return b == 0? a: gcd(b, a%b);
}
int main()
{
//freopen("in", "r", stdin);
    while(~scanf("%s", s)) {
        int len = strlen(s);
        if(s[0] == '0' && len == 1) break;

        ll sum = 0;
        len = 0;
        for(int i = 2; s[i] != '.'; ++i) {
            sum = sum * 10 + s[i]-'0';
            len++;
        }
        //printf("%lld\n", sum);
        ll num = sum, t = 1, up, ud;
        ll on, down;
        on = down = 1<<30;
        for(int i = 1; i <= len; ++i) {
            num /= 10;
            t *= 10;
            up = sum - num;
            ud = (ll)pow(10.0, len - i) * (t - 1);
            ll g = gcd(ud, up);
            if((ud / g) < down) {
                on = up/g;
                down = ud/g;
            }
        }
        printf("%I64d/%I64d\n", on, down);
    }
    return 0;
}