Hướng dẫn giải của Phép chia
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Chữ số thứ ~n~ sau dấu phẩy của ~a / b~ có thể tính bằng phép chia dài, hoặc bằng công thức dùng lũy thừa nhanh theo modulo ~b~.
Sub 1: Phép chia dài — ~O(n)~, dùng khi ~n \le 10^7~
Lấy phần dư ~r = a \bmod b~, lặp ~n~ lần: ~r \leftarrow 10r~, chữ số là ~\lfloor r/b \rfloor~, ~r \leftarrow r \bmod b~.
Nếu chỉ nộp sub này: đúng 6/10 test.
Sub 2: Lũy thừa nhanh — ~O(\log n)~
Chữ số thứ ~n~ là ~\lfloor 10 r / b \rfloor~ với ~r = (a \bmod b) \cdot 10^{n-1} \bmod b~. Tính ~10^{n-1} \bmod b~ bằng lũy thừa nhanh.
Nếu chỉ nộp sub này: đúng 10/10 test.
Chương trình hoàn chỉnh
Dữ liệu ~n \le 10^7~ dùng sub 1, còn lại dùng sub 2.
#include <bits/stdc++.h>
using namespace std;
long long a, b, n; // x = a / b, can tim chu so thu n sau dau phay
// Sub 1: mo phong phep chia dai, lay tung chu so. O(n). Dung khi n <= 10^7.
void sub1() {
long long r = a % b, digit = 0;
for (long long i = 1; i <= n; i++) {
r *= 10;
digit = r / b; // chu so thu i sau dau phay
r %= b;
}
cout << digit << "\n";
}
// Sub 2: chu so thu n = floor(10 * r / b) voi r = (a * 10^(n-1)) mod b.
// Tinh 10^(n-1) mod b bang luy thua nhanh, O(log n). Dung cho n rat lon.
void sub2() {
long long e = n - 1, base = 10 % b, pw = 1 % b;
while (e > 0) {
if (e & 1) pw = pw * base % b;
base = base * base % b;
e >>= 1;
}
long long r = (a % b) * pw % b;
cout << r * 10 / b << "\n";
}
int main() {
cin >> a >> b >> n;
if (n <= 10000000LL) sub1();
else sub2();
return 0;
}
Bình luận