exponent가 거의 INT_MAX에 근접하므로 일일이 b 번 곱하고 있으면 당연히 시간 초과가 날 것이다. 다음과 같이 modular 연산의 성질과 지수 법칙을 이용하면 exp/2를 계속 재귀 호출하면서 O(log N)으로 바운드 시킬 수 있다.
a^exp × a^exp = a^(2*exp)
a mod n * b mod n = (a * b) mod n
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll multi(ll x, ll y, ll z) {
if(y==1) return x % z;
ll ans = multi(x, y/2, z);
ans = ans * ans % z;
// y == odd
if(y&1) return x * ans % z;
// y == even
return ans % z;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
ll a, b, c;
cin >> a >> b >> c;
cout << multi(a, b, c);
}
지수가 짝수인지 홀수인지를 여부를 체크하기 위해 modular(%) 연산 대신 bitwise and(&) 연산을 사용했다. 1의 경우 LSB만 1이고 나머지 bit은 모두 0이므로 1과 bitwise and(&) 결과가 1이면 홀수, 0이면 짝수다. bitwise 연산의 cost가 더 적다는 것은 당연