자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.
첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다
지수 법칙을 이용하는 것이 핵심
10^10 을 구할 때, pow(10,10)은 10 10 10... 총 10번의 곱셈이 일어난다.
그러나 지수를 절반씩 나누어서 구하면 아래와 같다
int a,b,c;
// n에 대해 n^k를 리턴
int power(int n, int k){
if(k==0) return 1;
int temp = power(n,k/2);
int result = (1LL * temp * temp) % c; // n^k가 int의 범위를 벗어 날 수 있음으로 1LL를 곱해 long long으로 타입캐스팅 후 모듈러 연산을 수행한다.
// 홀수라면 n을 한번 더 곱해준다.
if(k%2) result = 1LL * result * n % c;
return result;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> a >> b >> c;
cout << power(a,b);
}