xiaoyu

题目描述

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

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

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

输入

一行三个整数:a b n,用空格分开。a是被除数,b是除数,n是所求的小数后位置(0<a,b,n<1000000000)

输出

一行3位数字,表示:a除以b,小数后第n位开始的3位数字。

样例输入

1
1 8 1

样例输出

1
125

样例输入

1
1 8 3

样例输出

1
500

解题思路

这个数据范围,只能模拟除法了

举个具体的例子:当我们要求 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
#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;
}

 评论