• 前言
• 题目大意
• 思路
• 代码
• 总结

前言

感觉挺有意思的，其实并不难，难的是思维。

题目大意

给出一个无限循环小数，求映射到分数上的分子和分母。

思路

看起来很复杂，但是可以分析哪里让我们很头疼。

我们会发现，如果是有限小数，那么就是直接乘以 $10^k$ 即可，$k$ 为小数位位数。无限小数让我们头疼的部分是在循环那里，所以我们要尝试把它消掉。

我们可以尝试从简单走到难。不妨选一个 $0.\dot{3}$，我们将它设为 $x$

然后我们希望可以消掉后面的部分，可以这样做：

$10x=3.\dots{3},10x-x=3.\dot{3}-0.\dot{3}=3$

$9x=3,x=\frac{3}{9}=\frac{1}{3}$

好像发现点什么了对吗，让我们看一个稍微复杂一点的，$0.1\dot{2}$ 吧，依然设为 $x$。

这个部分如果把 $1$ 消掉是不是就转成上面那个了呢？

$10x=1.\dot{2},100x=12.\dot{2}$

$100x-10x=12.\dot{2}-1.\dot{2}=11$

$90x=11,x=11/90$

好像已经发现规律了。但位数有点少，让我们把位数增多吧。$0.12\dot{3}\dot{6}$

$100x=12.\dot{3}\dot{6},10000x=1236.\dot{3}\dot{6}$

$10000x-100x=1224$

$9900x=1224,x=1224/9900$

我们已经找到规律了，为了让我们可以写出来，我们把规律总结一下：

设 $m$ 为不循环的部分的长度，$n$ 为循环节的长度，$x$ 为小数,$k$ 为小数的整数部分。

$\frac{k\cdot(10^{m+n}-10^m) +(\lfloor 10^{m+n}\cdot x\rfloor -\lfloor 10^m \cdot x\rfloor) }{10^{m+n}-10^m }$

代码

#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
double a;
ll t,n,m;
ll gcd(ll A,ll B){
    if(B==0){return A;}
    return gcd(B,A%B);
}
int main(){
    scanf("%lld",&t);
    for (int i = 1; i <=t ; ++i) {
        scanf("%lld%lld%lf",&n,&m,&a);
        ll k=a;
        n=m-n+1;
        m-=n;
        ll down=(pow(10,m+n)- pow(10,m));
        ll up=ll(k*down+ll(pow(10,m+n)*a)-ll(pow(10,m)*a));
        ll GCD= gcd(up,down);
        printf("%lld %lld\n",up/GCD, down/GCD);
    }
    return 0;
}

总结

本题的难点在于如何消掉无限循环小数的部分，还有归纳。