十一届蓝桥杯研究生组国赛-循环小数(数论)

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

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

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

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

针对纯循环小数:

  0.142857142857…，循环体为142857，该循环体有6位，有
$$\mathrm{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{array}{rl}0.114285742857& =0.11+0.0042857\\ & =\frac{11}{100}+\frac{42857}{99999\ast 100}\\ & =\frac{11\ast 99999+42857}{9999900}\\ & =\frac{11\ast (100000-1)+42857}{9999900}\\ & =\frac{1100000-11+42857}{9999900}\\ & =\frac{1142857-11}{9999900}\\ & =\frac{小数部分(算上循环体和非循环体)-非循环体部分(即前p-1位)}{10^q-10^{p-1}}\end{array}$$

   此时,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年第十一届国赛真题-循环小数

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