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;
}
}
2 bình luận nữa