---
tags: uva
---
# UVA 10555(dead-fraction)
https://onlinejudge.org/external/105/10555.pdf
## 1. 題目
此題為求小數化成最小的分數
Sample Input

0.2...
0.3...
0.474612399...
0

Sample Output

2/9
1/3
1186531/2500000

## 2. 想法
循環小數有2種純循環小數和混循環小數
(1)純循環小數 $$A=0.aaaaaaaa，其中a為n位整數$$
$$A=\frac{a}{10^n}+\frac{a}{10^{2n}}+\frac{a}{10^{3n}}+.....$$
利用等差數列
$$A=\frac{\frac{a}{10^n}}{1-\frac{1}{10^n}}=\frac{a}{10^n-1}$$
10^n-1剛好為n個9 所以
$$0.17171717...=\frac{17}{99}
\\0.627627...=\frac{627}{999}$$
(2)混循環小數 $$B=0.baaaaa....,其中a為n位整數,b為m位整數$$
$$B=0.b+\frac{0.aaaaaaa}{10^m}$$
$$\implies B=\frac{b}{10^m}+\frac{a}{10^m(10^n-1)}=\frac{(10^nb+a)-b}{10^m(10^n-1)}$$
分母是n個9+m個0，分子的話是不循環部分加上一個循環部分，然後減掉不循環部分
$$0.317171717...=\frac{317-3}{990}=\frac{314}{990}$$
$$0.2718281828...=\frac{271828-27}{999900}$$

## 3.實作
題目沒說從哪位開始循環 => 依小數長度窮舉

#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b)
{
    if (a == 0 || b == 0)
    {
        return a + b;
    }
    return gcd(b, a % b);
}
int pow_10(int n)
{
    int res = 1;
    for (int i = 0; i < n; i++)
    {
        res *= 10;
    }
    return res;
}
int main()
{
    string s;
    while (cin >> s && s != "0")
    {
        string digit = s.substr(2, s.size() - 5);
        int len = digit.size();
        long long n = stoi(digit);
        if (n == 0)
        {
            cout << "1/0\n";
            continue;
        }
        int beta = n;
        int mina = 1e9, minb = 1e9;
        for (int i = 1; i <= len; i++) //依小數長度窮舉
        {
            beta /= 10;
            int a = n - beta; 
            int b = pow_10(len) - pow_10(len - i); //n個9+m個0
            int d = gcd(a, b);
            a /= d;
            b /= d;
            mina = min(mina, a);
            minb = min(minb, b);
        }
        cout << mina << "/" << minb << "\n";
    }

    return 0;
}