Python蓝桥杯刷题-小数第n位详解

题目描述

我们知道，整数做除法时，有时得到有限小数，有时得到无限循环小数。

如果我们把有限小数的末尾加上无限多个 0，它们就有了统一的形式。

本题的任务是：在上面的约定下，求整数除法小数点后的第 n 位开始的 3 位数。

输入描述

输入一行三个整数：a b n，用空格分开。a 是被除数，b 是除数，n 是所求的小数后位置（0<a,b,n<10的9次方）

输出描述

输出一行 3 位数字，表示：a 除以 b，小数后第 n 位开始的 3 位数字。

分析

首先，我们得明确几个关键点：

1. 如何处理除法后的循环小数？比如像1/3=0.(3)这样的无限循环小数，如何快速定位到第n位？

2. 当小数部分是有限的时候，比如1/8=0.125，之后都是0，这时候如果n超过有效位数，后面的三位应该是0吗？

3. 题目中的n的范围很大，可能到1e9，所以直接进行除法计算然后取小数点后的位数是不现实的，必须找到数学方法或规律来快速定位。

我们来思考如何解决这些问题。

a除以b的结果的小数部分可以分为两种情况：有限小数和无限循环小数。但根据题目描述，题目将所有有限小数视为末尾有无限个0的形式。例如，0.125被视为0.125000...。因此，无论哪种情况，我们都可以将小数部分视为一个循环体，或者是有限小数后面跟着无限个0的循环。

那如何找到小数点后的第n位开始的三个数字呢？

我们先处理除法后的余数，找到小数部分的每一位。但由于n可能非常大，直接逐位计算到第n位是不现实的。必须找到数学上的规律，或者利用模运算的性质来快速定位。我们知道，当进行除法时，余数的重复出现会导致循环的开始。例如，计算1/7=0.(142857)，余数会依次出现1→3→2→6→4→5→1，循环开始。因此，如果能找到余数的循环周期，就能快速定位到第n位的位置。

但这里的问题可能不需要找到整个循环周期，而是直接通过计算余数来找到第n位。因为每次余数乘以10再除以b，得到下一位的数字，同时余数更新为新的余数。这个过程可以表示为：

对于第k位小数，余数r_k = (r_{k-1} * 10) % b，而该位的数字是 (r_{k-1} * 10) // b。

因此，要找到第n位，只需要计算到第n次余数，然后取该位的数字。但问题是，n可能非常大，比如1e9，直接迭代计算n次显然会超时。因此，必须找到一种快速计算到第n位余数的方法。

这时候，快速幂模运算派上用场。因为每次余数的计算相当于乘以10，再取模b。而这个过程可以视为求10的幂次模b的值，然后应用到初始余数上。

方法思路

1. 余数判断：首先计算 amod  b。如果余数为0，则所有小数位均为0，直接输出"000"。

2. 快速幂模运算：利用快速幂算法计算 ，以快速定位到第 n 位。

3. 逐位计算：通过余数逐位计算第 n、n+1、n+2 位的数字，并处理循环小数或后续全0的情况。

具体分析

1. 小数部分的规律：

   • 小数部分是通过不断将余数乘以10，再除以 b得到的。

   • 比如 1÷8：

     • 余数 1×10=10，10÷8=1（第1位是1），余数是 2。

     • 余数 2×10=20，20÷8=2（第2位是2），余数是 4。

     • 余数 4×10=40，40÷8=5（第3位是5），余数是 0。

2. 快速定位到第 n 位：

   • 直接逐位计算到第 n 位会很慢（比如 n=10的9次方）。

   • 我们可以用 快速幂 来快速计算 ，这样可以直接跳到第 n 位对应的余数。

3. 逐位生成数字：

   • 从第 n 位开始，通过余数逐位计算3位数字。

解决代码

a, b, n = map(int, input().split())
remainder = a % b  # 初始余数
if remainder == 0:  # 如果能整除，小数部分全是0print("000")
else:# 快速幂计算 10^(n-1) % b，快速跳到第 n 位power = pow(10, n - 1, b)# 计算第 n 位对应的余数current_remainder = (remainder * power) % b# 逐位生成3位数字digits = []for _ in range(3):digit = (current_remainder * 10) // b  # 当前位的数字digits.append(digit)current_remainder = (current_remainder * 10) % b  # 更新余数# 输出结果print(f"{digits[0]}{digits[1]}{digits[2]}")

该方法利用快速幂和模运算高效处理大数问题，时间复杂度为 O(log⁡n)，适用于极大范围的输入。

 例子

我们可以换个例子再感受一下：

• a=3，b=7，n=4。

• 我们需要找到 3÷7 的小数部分从第4位开始的连续3位数字。

小数部分的生成规律

首先，我们来看 3÷7 的小数部分是如何生成的：

1. 余数 3×10=30，30÷7=4（第1位是4），余数是 2。

2. 余数 2×10=20，20÷7=2（第2位是2），余数是 6。

3. 余数 6×10=60，60÷7=8（第3位是8），余数是 4。

4. 余数 4×10=40，40÷7=5（第4位是5），余数是 5。

5. 余数 5×10=50，50÷7=7（第5位是7），余数是 1。

6. 余数 1×10=10，10÷7=1（第6位是1），余数是 3。

7. 余数 3×10=30，30÷7=4（第7位是4），余数是 2。

8. 以此类推，小数部分为 0.428571428571...，循环节是 428571。

如果我们直接逐位计算到第4位，需要计算4次。但如果 nn 很大（比如 n=109n=109），逐位计算会非常慢。快速幂 的作用是帮助我们快速计算出第4位对应的余数，从而跳过前面的计算。

我们需要计算 ，即 10的3次方mod  7。

1. 将指数 3 表示为二进制形式：。

2. 通过平方和乘法快速计算 10的3次方：

   • 。

   • 。

   • 

3. 计算 1000mod  7：

   • 1000÷7=142余 6，所以 1000mod  7=6。

跳到第4位

1. 初始余数：3mod  7=3。

2. 快速幂计算：10的3次方 mod  7=6。

3. 跳到第4位对应的余数：(3×6)mod  7=18mod  7=4。

4. 逐位生成数字：

   • 第4位：(4×10)÷7=5，余数是 5。

   • 第5位：(5×10)÷7=7，余数是 1。

   • 第6位：(1×10)÷7=1，余数是 3。

5. 输出结果：571。

关于快速幂相关知识，参考快速幂知识点