我们知道有理数可以写成有限小数和无限循环小数。无理数必然是无限不循环小数。下面对这个问题详细的分析并且给出相应的有理数转化成小数的代码。
回顾一下我们怎么做除法的，我们设 $p,q$ 为正整数。计算 $\frac{q}{p}$。首先给出两个显然的结论：
- $\frac{q}{p}$ 是整数，当且仅当 $p|q$；
- $\frac{q}{p}$ 是有限小数，当且仅当 $\exists n, s.t p|10^n*q$。
我们把注意力放在结果是无限循环小数的情况上。
那么为什么分数一定可以表示为循环小数呢？
因为我们一直计算后余数总在 $0,p-1$ 之间，那么经过 $p$ 次计算后一定会与之前的的某一个一样，那么自此以后后来的结果自然也就一样了，也就产生了循环的现象。即我们需要找到最小的正整数 $m,n$ 使得 $10^m \equiv 10^(n+m) \mod p$。即 $10^m(10^n-1) \equiv 0 mod p$。由于 $gcd(2,10^n-1)=gcd(5,10^n-1)=1$。因此，除掉 $p$ 中包含 $2,5$ 的因子。则 $10^n-1 \equiv 0 mod p$。此方程一定有解。并且若$p$是素数，且$10$是 $p$ 的原根，则 $n=p-1$。说了这么多其实也是废话，还是看代码吧，代码里包含了所有细节。
string rational(int n,int m){
if(m==0) return "";
string r;
if(m<0) n=-n,m=-m;
if(n<0){
n=-n;
r.push_back('-');
}
int t = n/m; // get the integer part of n/m
if(t==0) r.push_back('0');
while(t){
r.push_back(t%10+'0');
t/=10;
}
r.reserve();
n%=m;
if(n==0) return r;
r.push_back('.');
t = __gcd(n,m);
n/=t;m/=t;
while(m%10==0){
m/=10;
r.push_back(n/m+'0');
n%=m;
}
while(m%2==0){
m/=2;n*=5;
r.push_back(n/m+'0');
n%=m;
}
while(m%5==0){
m/=5;n*=2;
r.push_back(n/m+'0');
n%=m;
}
if(m==1) return r;
r.push_back('(');
t=1;
do{
r.push_back(10*n/m+'0');
n=10*n%m;
t=10*t%m;
}while(t!=1);
r.push_back(')');
return r;
}