时间限制: 1 Sec 内存限制: 128 MB 提交: 86 解决: 44 [提交][状态][讨论版]
ZhouZhentao的数学很差很差，最近他在复习《小学数学》中的有理数部分，但是他遇到了困难，因此请机智的你们来帮忙了。
课本上写着这样一道题：
无限循环小数是有理数，有理数都可以表示成分数形式。
现在给出一个无限循环小数 A（0<A<1），请你计算A的最简分数形式。
为了方便，我们用X表示无限循环小数A的循环节：
例如 X=3 时，对应的小数A是 0.333333......
例如 X=333 时，对应的小数A也是 0.333333......
例如 X=28 时，对应的小数A是 0.282828......
例如 X=123456789 时，对应的小数A是 0.123456789123456789......
现在给定一个X，请你输出X对应的无限循环小数A的最简分数形式。
例如：输入6，表示的小数是0.666666...... 最简分数形式是2/3，你应该输出2/3。 【知识拓展】
[1]最简分数：分子、分母只有公因数1的分数，或者说分子和分母互质的分数，叫做最简分数，又称既约分数。如：三分之二，九分之八，八分之三等等。
[2]在数学上，0.999999………等于1，最简分数形式是1/1。
多组测试数据（大约100组），每组测试数据输入一个整数 X，表示无限循环小数A的循环节为X。（0 < X < 99999，并且x不会等于9、99、999、9999）
每组测试数据输出一行，形如p/q（p与q互质），表示无限循环小数A的最简分数。
输入6，表示的小数是0.666666...... 最简分数形式是2/3。
int gcd(int a,int b) { if(b==0) return a; return gcd(b,a%b); } a为分母,b为分子
找到最大公约数
复杂度大约为O（log max(a,b)）
#include <bits/stdc++.h> using namespace std; int b[10]; int yuefen(int x,int y) { if(y==0) return x; return yuefen(y,x%y); } int main() { int a; while(~scanf("%d",&a)) { memset(b,0,sizeof(b)); int k=1; while(1) { b[k++]=a; a=a/10; if(a==0) break; } int fz=0; int fm=0; for(int i=k-1; i>=1; i--) { fz=fz*10+b[i]; fm=fm*10+9; } int c=yuefen(fm,fz); printf("%d/%d\n",fz/c,fm/c); } return 0; }
