蓝桥杯国赛 小数第n位(数论)
题目描述
我们知道,整数做除法时,有时得到有限小数,有时得到无限循环小数。
如果我们把有限小数的末尾加上无限多个 0,它们就有了统一的形式。
本题的任务是:在上面的约定下,求整数除法小数点后的第 n 位开始的 3 位数。
输入描述
输入一行三个整数:a b n,用空格分开。a 是被除数,b 是除数,n是所求的小数后位置(0 < a , b , n <
输出描述
输出一行 3 位数字,表示:a 除以 b,小数后第 n 位开始的 3 位数字。
输入输出样例
示例
输入
1 8 1
输出
125
运行限制
- 最大运行时间:1s
- 最大运行内存: 256M
思路 🤔
这道题一开始来说,我是没什么思路的,第一个想的就是可以根据python的特性,直接打出后面的数字,就可以得出答案了,不过这方法都是答案错误的,可能由于题目中有一个补0的操作,所以导致错误。
接着就是一个暴力法,题目要求第n位的后三位,很显然只要我们把它变成整数,再%1000就可以了;其实也不一定非要全部变成整数,并且对于循环小数也是不可能变成整数的。所以我们只需要把第n+2位之前变成整数,%1000就可以了。,这样就可以解决我们的问题了,但是之后提交后,发现这个只能过60%的数据,后面的都是因为时间超限的,毕竟是暴力法。
# 暴力法求解 a,b,n = map(int,input().split()) s = '' a = a%b while len(s) < n+2: a = a*10 s += str(a//b) a = a%b print(s[-3:])
根据前面的思路,实际上,我们就可以把答案转化为以下的公式
可以看到这个其实就是一个求逆元的操作,由于我们的模是1000,不是素数,不能使用费马小定理和扩展欧几里得来求逆元。所以可以转化为以下公式求
最后难点就在于求幂了,所以最后只要写一个快速幂的方法,就可以得出最后的结果,最后还要注意一个就是不足的需要补0
a,b,n = map(int,input().split()) def qpow(a,b,mod): ans = 1 while b: if b&1: ans = ans*a%mod a = a*a%mod b = b>>1 return ans mod = 1000*b x = a*qpow(10,n+2,mod)%mod//b print("%03d"%x)