CSES - Exponentiation II | Lũy thừa II
Xem PDF
Điểm:
1400 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Việc của bạn là tính toán hiệu quả giá trị \(a^{b^c}\) modulo \(10^9 + 7\).
Lưu ý rằng trong bài này, ta cho rằng \(0^0 = 1\).
Input
- Dòng đầu tiên là một số nguyên \(n\): số lượng phép tính.
- Tiếp theo là \(n\) dòng, mỗi dòng chứa ba số nguyên \(a, b\) và \(c\).
Output
- In ra từng giá trị \(a^{b^c}\) modulo \(10^9+7\).
Constraints
- \(1 \le n \le 10^5\)
- \(1 \le a,b,c \le 10^9\)
Example
Sample input
3
3 7 1
15 2 2
3 4 5
Sample output
2187
50625
763327764
Bình luận
include <bits/stdc++.h>
define ll long long
using namespace std;
const ll mod = 1e9 + 6;
const ll MOD = 1e9 + 7;
ll n, a, b, c;
ll lt( ll a, ll b, ll mod){
if ( b == 0) return 1;
ll x = b / 2;
a %= mod;
ll ch = lt(a, x, mod) % mod;
if ( b & 1){
return ((ch * ch) % mod * (a % mod)) % mod;
}
else{
return (ch * ch) % mod;
}
}
int main()
{
cin >> n;
while ( n--){
ll a, b, c; cin >> a >> b >> c;
ll x = lt(b, c, mod);
cout << lt(a, x, MOD) << endl;
}
}
Note
\(C ≡ D\) (module m) không có nghĩa là \(A^C\) ≡ \(A^D\) (module m). Ví dụ \(2^3\) ≢ \(2^5\) (module 3)
Nhưng nếu \(C ≡ D\) (mod \(φ(n)\)) với \(φ\) là hàm phi Euler, thì \(A^C\) ≡ \(A^D\) (mod \(n\)) nếu như \(A\) nguyên tố cùng nhau với \(n\)
(Theo wikipedia, xem qua tại đây)
Hãy tính toán các giá trị \(a^{b^c} \space\) \(mod\) \(\space 10^9 +7\) một cách hiệu quả.
Lưu ý: trong bài này, ta giả định rằng \(0^0 = 1\).
Input
Output
Constraints
Example
Test
Input
Output
Note