小数第n位
题目描述
我们知道,整数做除法时,有时得到有限小数,有时得到无限循环小数。
如果我们把有限小数的末尾加上无限多个 0,它们就有了统一的形式。
本题的任务是:在上面的约定下,求整数除法小数点后的第
n
n
n 位开始的 3 位数。
输入描述
输入一行三个整数:
a
,
b
,
n
a , b , n
a,b,n,用空格分开。
a
a
a 是被除数,
b
b
b 是除数,
n
n
n 是所求的小数后位置(
0
<
a
,
b
,
n
<
1
0
9
0<a,b,n<10^9
0<a,b,n<109)
输出描述
输出一行 3 位数字,表示:
a
a
a 除以
b
b
b,小数后第
n
n
n 位开始的 3 位数字。
输入输出样例
示例
输入
1 8 1
输出
125
运行限制
难度: 中等 标签: 数论, 快速幂, 2017, 国赛
分析:
- 蓝桥题目:小数第n位
-
d
o
u
b
l
e
double
double 的精度不够,它可以表示十进制的15或16位有效数字,对于无限小数来说,这是明显不够的。
- 公式转换
a
b
%
p
=
a
%
(
b
×
p
)
b
(
1
)
\begin{aligned} % requires amsmath; align* for no eq. number \frac{a}{b}\%p=\frac{a\%(b\times p)}{b} &(1) \end{aligned}
ba%p=ba%(b×p)(1)
a
b
×
1
0
n
+
2
%
1
0
3
=
a
×
1
0
n
+
2
b
%
1
0
3
=
a
×
1
0
n
+
2
%
(
b
×
1
0
3
)
b
=
(
a
%
(
b
×
1
0
3
)
)
×
(
1
0
n
+
2
%
(
b
×
1
0
3
)
)
b
\begin{aligned} % requires amsmath; align* for no eq. number \frac{a}{b}\times 10^{n+2}\%10^3&=\frac{a\times10^{n+2}}{b}\%10^3\\ &=\frac{a\times 10^{n+2}\%(b\times 10^3)}{b}\\ &=\frac{(a\%(b\times 10^3))\times(10^{n+2}\%(b\times 10^3))}{b} \end{aligned}
ba×10n+2%103=ba×10n+2%103=ba×10n+2%(b×103)=b(a%(b×103))×(10n+2%(b×103))
代码
import java.util.Scanner;
public class Main {
public static long quickPow(long a,long b,long p) {
long ans = 1l;
while (b!=0){
if ((b&1)==1) ans = ans*a%p;
b>>=1;
a = a*a%p;
}
return ans;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
long a = scanner.nextLong();
long b = scanner.nextLong();
long n = scanner.nextLong();
long bb = b*1000;
System.out.println((a%bb*quickPow(10,n+2,bb)%bb)/b);
}
}
参考材料
小数第n位–蓝桥