POJ 1930 数学

链接：

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

题意：

给你一个无限循环小数，转换成分数，要求分母最小

题解：

打死我都不信这是小学的奥数题

百度百科有方法：

http://baike.baidu.com/link?url=30XLCYc644bWk-VDr3g2wxxvIWGxpgpZ22lbt4GF6msQubW-OMjSvrZ3TH-9ztOIQnN2dJUak5t1I1FXL9PUrM9P1EpNEjE2ILBTZQeyBlYjn5BW0jatLWbkeumjPqd0JWJWOBBzUCvJLP7ZDG8blFzCaIDurUEVtplt47b5OyJSuuVkudIibQrImloU-YGT

套公式法
纯循环
用9做分母，有多少个循环数就几个9，比如0.3，3的循环就是9分之3，0.654，654的循环就是999分之654， 0.9，9的循环就是9分之9（1），以此类推。
混循环
先来看几个例子
例：把混循环小数0.228˙化为分数：
解：0.228˙
=[（228/1000）+8/9000）]
=228/（900+100）+8/9000
=[（228/900）-（228/9000）]+（8/9000）
=（228/900）+[（8/9000）-（228/9000）]
=（228/900）-（22/900）
=（228-22）/900
=206/900
=103/450；
例：把混循环小数0.123˙68˙化成分数：
解：0.123˙68˙=(0.12368+0.00000˙68˙)
=(12368/100000)+（68/9900000）
=[（12368/99000）-（12368/990000）]+（68/9900000）
=（12368/99000）+[（68/9900000）-（12368/9900000）]
=（12368/99000）-（12300/9900000）
=(12368-123)/99000
公式
用9和0做分母，首先有一个循环节有几位数字就几个9，接着有几个没加入循环的数就加几个0，再用第二个循环节以前的小数部分组成的数与小数部分中不循环部分组成的数的差做分子，比如0.43，3的循环，有一位数没加入循环，就在9后面加一个0做分母，再用43减4做分子，得 90分之39，0.145，5的循环就用9后面加2个0做分母，再用145减14做分子，得900分之131，0.549，49的循环，就用99后面加1个0做分母，用549减5做分子，最后得990分之545，以此类推，能约分的要化简。

代码：

 1 #include <map>
 2 #include <set>
 3 #include <cmath>
 4 #include <queue>
 5 #include <stack>
 6 #include <cstdio>
 7 #include <string>
 8 #include <vector>
 9 #include <cstdlib>
10 #include <cstring>
11 #include <sstream>
12 #include <iostream>
13 #include <algorithm>
14 #include <functional>
15 using namespace std;
16 #define rep(i,a,n) for (int i=a;i<n;i++)
17 #define per(i,a,n) for (int i=n-1;i>=a;i--)
18 #define all(x) (x).begin(),(x).end()
19 #define pb push_back
20 #define mp make_pair
21 #define lson l,m,rt<<1  
22 #define rson m+1,r,rt<<1|1 
23 typedef long long ll;
24 typedef vector<int> VI;
25 typedef pair<int, int> PII;
26 const ll MOD = 1e9 + 7;
27 const int INF = 0x3f3f3f3f;
28 const int MAXN = 1010;
29 // head
30 
31 int gcd(int a, int b){
32     return b == 0 ? a : gcd(b, a%b);
33 }
34 
35 int main(){
36     string s;
37     while (cin >> s){
38         if (s == "0")  break;
39         string digit = s.substr(2, s.length() - 5);
40         int n = digit.length();
41         int m = atoi(digit.c_str());    
42         int a, b = 1 << 30;
43         rep(i, 0, n) {
44             string cnt = digit.substr(0, i);
45             int aa = m - atoi(cnt.c_str());
46             int bb = pow(10, n) - pow(10, i);
47             int t = gcd(aa, bb);
48             aa /= t;
49             bb /= t;
50             if (b > bb) a = aa, b = bb;
51         }
52         cout << a << "/" << b << endl;
53     }
54     return 0;
55 }