1. 문제
https://www.acmicpc.net/problem/1629
2. 풀이
2.1. 비효율적인 풀이
- 제곱수를 짝수일 경우 2개로 나누고, 홀수일 경우 짝수, 홀수 자식으로 만들어서 재귀함수를 호출합니다.
- 아래의 소스코드는 자식이 많아지는 경우에 시간 초과가 납니다.
- 메모이제이션이나 2.2의 문제풀이 방법을 참고해주세요.
#define _CRT_SECURE_NO_WARNINGS
#include<algorithm>
#include<iostream>
using namespace std;
int a, b, c;
long long pow(int x, int y, int z) {
if (y == 1) return x % z;
if (y % 2 == 0) return (pow(x, y / 2, z) * pow(x, y / 2, z)) % z;
else return (pow(x, y / 2, z) * pow(x, 1 + y / 2, z)) % z;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> a >> b >> c;
cout << pow(a, b, c);
}
2.2. 효율적인 풀이
- 제곱수를 짝수일 경우 절반으로 떨어뜨리는 방법을 사용하고, 홀수일 경우 짝수로 만들어서 속도를 매우 빠르게 할 수 있습니다.
#include<iostream>
using namespace std;
long long int a, b, c;
long long int pow(long long int x, long long int y){
if(y==0) return 1;
if(y==1) return x;
if(y % 2 == 1) return (pow(x, y-1)*x) % c;
long long int half = pow(x, y/2);
return (half * half) % c;
}
int main(){
cin>>a>>b>>c;
cout<<pow(a,b)%c;
return 0;
}