1303: Decimal
Time Limit: 1 Sec Memory Limit: 128 MB[Submit][Status][Web Board]
Description
任意一个分数都是有理数,对于任意一个有限小数,我们都可以表示成一个无限循环小数的形式(在其末尾添加0),对于任意一个无限循环小数都可以转化成一个分数。现在你的任务就是将任意一个无限循环小数转化成既约分数形式。所谓既约分数表示,分子和分母的最大公约数是1。
Input
有多组数据。
每组数据一行。输入为0.a1a2a3...ak(b1b2...bm)的形式,其中a1a2a3...ak为非循环部分,(b1b2b3..bm)为循环部分。数据保证非循环部分的长度k和循环部分的长度m不会超过8.
Output
对于每组测试数据输出A/B,其中A是分子,B是分母,A,B均为整数。
Sample Input
0.0(714285)
0.0(5)
0.9(671)
Sample Output
1/14
1/18
4831/4995
让我想起我在北京教奥数的日子了。
p = 0.a1a2a3...ak(b1b2...bm)
A = p*10^k = a1a2a3...ak.(b1b2...bm)
B = p*10^(k+m) = a1a2a3...akb1b2...bm.(b1b2...bm)
B-A = p(10^(k+m)-10^(k))为整数
p = (B-A)/(10^(k+m)-10^(k));
A = p*10^k = a1a2a3...ak.(b1b2...bm)
B = p*10^(k+m) = a1a2a3...akb1b2...bm.(b1b2...bm)
B-A = p(10^(k+m)-10^(k))为整数
p = (B-A)/(10^(k+m)-10^(k));
#include <iostream> #include <stdio.h> #include <queue> #include <stdio.h> #include <string.h> #include <vector> #include <queue> #include <set> #include <algorithm> #include <map> #define Max(a,b) ((a)>(b)?(a):(b)) using namespace std ; typedef long long LL ; LL gcd(LL x ,LL y){ return y==0?x:gcd(y,x%y) ; } LL my_pow(LL x ,int y){ LL sum=1 ; for(;y;y>>=1){ if(y&1) sum*=x ; x*=x ; } return sum ; } int main(){ int x ,y ,L_a ,L_b; string str ,A ,B; LL fenzi ,fenmu; LL ab ,a ; while(cin>>str){ for(int i=0;i<str.length();i++){ if(str[i]=='(') x=i ; } A="" ; B="" ; A=str.substr(2,x-2) ; B=str.substr(x+1,str.length()-x-2) ; L_a=A.length() ; L_b=B.length() ; ab=a=0 ; for(int i=0;i<A.length();i++){ ab=ab*10+A[i]-'0' ; } for(int i=0;i<B.length();i++){ ab=ab*10+B[i]-'0' ; } for(int i=0;i<A.length();i++){ a=a*10+A[i]-'0' ; } if(B==""){ fenzi=a ; fenmu=my_pow((LL)10,L_a) ; } else{ fenzi=ab-a ; fenmu=my_pow((LL)10,L_a+L_b)-my_pow((LL)10,L_a) ; } LL temp=gcd(fenzi,fenmu) ; fenzi/=temp ; fenmu/=temp ; cout<<fenzi<<"/"<<fenmu<<endl ; } return 0 ; }