Hướng dẫn giải của Phép tính lũy thừa
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
Tính ~a^b \cdot b^a \bmod m~ với ~a, b, m \le 10^{18}~. Tích có thể vượt 64 bit nên mỗi phép nhân modulo dùng kiểu __int128.
Sub 1: Nhân lặp — ~O(a + b)~, dùng khi ~a, b \le 10^6~
Tính lũy thừa bằng cách nhân lặp đúng số mũ lần, mỗi lần lấy modulo.
Nếu chỉ nộp sub này: đúng 10/20 test.
Sub 2: Lũy thừa nhanh — ~O(\log a + \log b)~
Bình phương và nhân theo các bit của số mũ. Kết quả cuối là tích hai lũy thừa mod ~m~.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm main đọc dữ liệu rồi chọn sub theo kích thước: dữ liệu nhỏ gọi sub 1 (vét cạn), dữ liệu lớn gọi sub cuối. Khi đi thi, nên nộp đầy đủ như vậy: nếu sub sau sai hoặc chưa kịp làm thì vẫn ăn điểm các sub trước.
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
// Nhân modulo m; tích có thể vượt 64 bit nên tính bằng __int128
ull mulmod(ull x, ull y, ull m) {
return (ull)((unsigned __int128)x * y % m);
}
// Sub 1: vét cạn — nhân lặp e lần, O(e). Dùng khi số mũ <= 10^6
ull powLoop(ull x, ull e, ull m) {
ull r = 1 % m;
x %= m;
for (ull i = 0; i < e; i++) r = mulmod(r, x, m);
return r;
}
// Sub 2: lũy thừa nhanh (bình phương và nhân theo bit của số mũ), O(log e)
ull powFast(ull x, ull e, ull m) {
ull r = 1 % m;
x %= m;
while (e > 0) {
if (e & 1) r = mulmod(r, x, m);
x = mulmod(x, x, m);
e >>= 1;
}
return r;
}
ull a, b, m;
// a^b * b^a mod m, tính bằng hàm lũy thừa đã chọn
void sub1() {
cout << mulmod(powLoop(a, b, m), powLoop(b, a, m), m) << "\n";
}
void sub2() {
cout << mulmod(powFast(a, b, m), powFast(b, a, m), m) << "\n";
}
int main() {
freopen("POWEXP.INP", "r", stdin);
freopen("POWEXP.OUT", "w", stdout);
cin >> a >> b >> m;
if (a <= 1000000 && b <= 1000000) sub1(); // số mũ nhỏ: nhân lặp
else sub2();
return 0;
}
Bình luận