Description

孤单的zydsg又一次孤单的度过了520，不过下一次不会再这样了。zydsg要做些改变，他开始尝试和无限循环小姐姐约会。无限循环小姐姐给了zydsg一个无限循环小数，当zydsg把这个循环小数化为分数后，分母就代表小姐姐有空的时间。例如小姐姐3天后有空，可能就会给zydsg”0.3333…”。但是，由于小姐姐给zydsg的小数没有指定循环节，所以可能有多种情况，例如“0.20…”的循环节可能是“0”，也可能是“20”。为了尽早跟小姐姐约会，zydsg会单方面的选择最早的约会日期（分母最小的情况）。那么你现在能帮zydsg确定循环小姐姐给的循环小数对应的分数吗？

Input

多组数据，每组数据只有一行形如 “0.dddd…” 其中dddd代表不超过9位的由0-9组成的数串，但不全为零。最后一行为0代表输入结束

Output

对于每一组数据，输出化为的分母最小的分数

Sample Input

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

Sample Output

2/9
1/3
1186531/2500000

题解

首先循环小数有两种，纯循环小数和混循环小数，先考虑前一种。
$(α，β可以代表多位数, 比如α=2，那么n=1, α=13，那么n=2,α=523，那么n=3，同理β和m的关系也是如此)$

• 考虑小数其中是一个n位整数.那么就可以写成分数求和形式:
  
  利用等比数列求和公式:
  

恰好是n个9，因此一个循环节长度为n的纯循环小数，化成分数的话，分子是循环节，分母是n个9.

举个例子：

• 那么再来看混循环小数，也就是小数其中是一个n位整数，是一个m位整数.
  
  利用上一步的结果，就有
  
  分母是n个9后面拼上m个0， 分子的话，恰好是不循环部分拼上一个循环节，然后后面再减掉一个不循环部分.

因此一个循环节长度为n，不循环部分长度为m的混循环小数，化成分数的话，分母是n个9拼上m个0，分子是不循环部分和一个循环节拼起来的数减掉不循环部分.

举个例子:

关键点在于题目循环小数到底从哪一位开始没有明说，所以无脑暴力穷举一遍就行了。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<sstream>
#include<set>
#include<bitset>
#include<vector>
#include<cmath>
using namespace std;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
typedef pair<int,int> PII;
typedef long long LL;
const int INF=0x3f3f3f3f;

const int N=20;
char s[N];
int p[N];

int gcd(int a,int b)
{
    if(!b) return a;
    return gcd(b,a%b);
}

void init()
{
    p[0]=1;
    for(int i=1;i<=9;i++)
        p[i]=p[i-1]*10;
}

int main()
{
    init();
    while(scanf("%s",s))
    {
        if(!strcmp(s,"0")) break;

        int num=0;
        int len=0;
        for(int i=2;s[i]!='.';i++)
        {
            num=num*10+(s[i]-'0');
            len++;
        }

        int belta=num;
        int mina=1e9,minb=1e9;
        for(int i=1;i<=len;i++)
        {
            belta/=10;
            int a=num-belta;
            int  b=p[len-i]*(p[i]-1);

            int t=gcd(a,b);

            if(b/t < minb)
            {
                mina=a/t,minb=b/t;
            }
        }
        cout<<mina<<'/'<<minb<<endl;
    }
   // system("pause");
}