1、题目描述

已知 S 是一个小于 11 的循环小数，请计算与 S 相等的最简真分数是多少。

例如 0.3333⋯0.3333⋯ 等于 1331 ，0.1666⋯0.1666⋯ 等于 1661 。

输入描述

输入第一行包含两个整数 p 和 q，表示 S 的循环节是小数点后第 p 位到第 q位。

第二行包含一个 q 位数，代表 S 的小数部分前 q 位。

其中，1≤p≤q≤10。

输出描述

输出两个整数，用一个空格分隔，分别表示答案的分子和分母。

输入输出样例

示例 1

输入

1 6
142857

输出

1 7

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

2、解题思路

这里参考了别的文章说有个定理：纯循环小数转化位分数，就等于循环体部分除以与循环体位数相同的9,例如 $0.42857=\frac{42857}{99999}$。

先解释下输入样例，

1 6
142857

代表原小数为$0.142857142857…=\frac{1}{7} $

无限循环小数分为纯循环小数，即0.142857142857…,以及混合循环小数：0.114285742857…等。

我们通过计算与化简说明怎样得到这个结果

针对纯循环小数:

0.142857142857…，循环体为142857，该循环体有6位，有

$$0.142857142857...=\frac{142857}{999999}=\frac{142857}{10^6-1}=\frac{循环体}{10^q-1}$$

此时p=1,q=6，循环体位142857

再计算出142857与999999的最大公约数位142857，则对分数 $\frac{142857}{999999}$化简得到 $\frac{1}{7}$。

针对混合循环小数:

\begin{align} 0.1142857&=0.11+0.42857\\ &=\frac{11}{100}+\frac{42857}{99999*100}\\ &=\frac{11*99999+42857}{9999900}\\ &=\frac{11*(100000-1)+42857}{9999900}\\ &=\frac{1100000-11+42857}{9999900}\\ &=\frac{1142857-11}{9999900}\\ &=\frac{小数部分(算上循环体和非循环体)-非循环体部分(即前p-1位)}{10^q-10^{p-1}} \end{align}

此时,p=3,q=7

其实纯循环小数和混合循环小数最后的推导结果是可以合并的，这里为了区分就不合并了，看起来思路还清晰一点。

3、代码实现

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int p = scan.nextInt();
        int q = scan.nextInt();
        long decimal = scan.nextLong();

        if(p==1){   //纯循环小数
            //分子
            long x=decimal;
            //分母
            long y=(long)Math.pow(10,q)-1;
//            System.out.println("x="+x);
//            System.out.println("y="+y);
            System.out.println(x/gcd(x,y)+" "+y/gcd(x,y));
        }else{  //混合循环小数
            //取出decimal的前(p-1)位
            String s = String.valueOf(decimal);
            String sub = s.substring(0, p-1);
            long tmp = Long.parseLong(sub);
            //分子
            long x=decimal-tmp;
            //分母
            long y=(long)Math.pow(10,q)-(long)Math.pow(10,p-1);
//            System.out.println("x="+x);
//            System.out.println("y="+y);
            System.out.println(x/gcd(x,y)+" "+y/gcd(x,y));
        }


        scan.close();
    }
    public static long gcd(long a,long b){
        if(b==0){
            return a;
        }
        long max=Math.max(a,b);
        long min=Math.min(a,b);
        return gcd(min,max%min);
    }
}

测试 $0.142857142857$，结果为 $\frac{1}{7}$

测试 $0.114285742857$，结果为 $\frac{571423}{4999950}$

本文参考了如下大佬的解题思路：

蓝桥杯2020年第十一届国赛真题-循环小数

第十一届蓝桥杯（决赛）之循环小数