题目地址:http://poj.org/problem?id=1930

题目大意

给你一个循环小数,化成分数,要求分数的分母最小。

思路

这题比较坑,没有告诉你循环部分。。只能暴力搜一遍。。

先来说说怎么把循环小数话分数吧。

纯循环小数化分数

纯循环小数的小数部分可以化成分数,这个分数的分子是一个循环节表示的数,分母各位上的数都是9,9的个数与循环节的位数相同。能约分的要约分。

例:
$$0.\dot 23\dot 3 = \dfrac{233}{999}$$

混循环小数化分数

这个分数的分子是第二个循环节以前的小数部分组成的数与小数部分中不循环部分组成的数的差。分母的头几位数是9,末几位是0。9的个数与循环节中的位数相同,0的个数与不循环部分的位数相同。

例:

$$0.666\dot 23 \dot 3 = \dfrac{666233-666}{999000} = \dfrac{665567}{999000}$$

回到问题

将题目小数部分提取出来,从后往前搜索,后面部分作为循环部分,前面部分作为不循环部分。按上述方法求出分子分母,记录最小分母即可。。

AC代码

/*************************************************************************
    > File Name: 1930.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-12-08 二 20:43:29 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <limits>
#include <utility>
#include <cstring>
using namespace std;
typedef long long ll;

ll gcd(ll a, ll b) {
    return b==0?a:gcd(b, a%b);
}
ll pow_10(int n) {
    ll s=1;
    for(int i=0; i<n; ++i) s*=10;
    return s;
}

string n;
void solve() {
    n.erase(0, 2);
    n.erase(n.length()-3, 3);
    if(atoi(n.c_str()) == 0) {
        puts("0/1");
        return;
    }

    ll x=0, y=1;
    ll min_x = 0, min_y = numeric_limits<ll>::max();
    // cout << string("2333").substr(0, 2) << endl;

    for(int i=n.length(); i>=1; --i) {
        x = atoi(n.c_str()) - atoi(n.substr(0, i-1).c_str()); // 分子,第二个循环部分前面的数字减去不循环部分
        y = ll(pow_10(n.length())) - ll(pow_10(i-1));  // 分母,9的个数为循环部分长度,0的个数为不循环部分长度
        // printf("%lld/%lld\n", x, y);
        ll Gcd = gcd(x, y); // 约分化简
        x/=Gcd;
        y/=Gcd;
        if(y<min_y) {
            min_y = y;
            min_x = x;
        }
    }
    printf("%lld/%lld\n", min_x, min_y);
}

int main()
{
#ifdef Oj
    freopen("1930.in", "r", stdin);
#endif
    while(cin >> n) {
        if(n=="0") break;
        solve();
    }
    return 0;
}