题目描述
我们知道，整数做除法时，有时得到有限小数，有时得到无限循环小数。
如果我们把有限小数的末尾加上无限多个0，它们就有了统一的形式。
本题的任务是：在上面的约定下，求整数除法小数点后的第n位开始的3位数。
输入
一行三个整数：a b n，用空格分开。a是被除数，b是除数，n是所求的小数后位置（0<a,b,n<1000000000）
输出
一行3位数字，表示：a除以b，小数后第n位开始的3位数字。
样例输入
样例输出
样例输入
样例输出
解题思路
这个数据范围，只能模拟除法了
举个具体的例子：当我们要求 1 / 7 的第二位小数4时，
具体过程相当于是 1 % 7 * 10 % 7 * 10 / 7，
取模与乘法运算满足交换律 且 a % m * b % m = a * b % m
因此上面这个式子以又可以写成 1 * 10^(2-1) % 7 * 10 / 7
由于这个n也是巨大的，常规求幂的方式行不通，所以肯定要用到快速幂
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| #include<iostream>
using namespace std;
long long gcd(long long m, long long n) {
return m % n == 0 ? n : gcd(n, m % n);
}
long long quick_pow(long long n, long long k, long long mod) {
long long res = 1, base = n % mod;
while (k) {
if (k & 1) res = (res % mod) * (base % mod) % mod;
base = ((base % mod) * (base % mod)) % mod;
k >>= 1;
}
return res;
}
int main() {
long long m, n, k1, k2;
cin >> m >> n >> k1;
k2 = k1 + 2;
long long gcd_mn = gcd(m, n);
m /= gcd_mn, n /= gcd_mn;
long long res = (m * quick_pow(10, k1 - 1, n)) % n;
for (long long i = k1; i <= k2; i++) {
res *= 10;
cout << res / n;
res %= n;
}
return 0;
}
|