문제
풀이
브루트포스로 하면 시간초과가 나는 문제이다. 분할정복을 통해, 거듭제곱 연산으로 바꾸어 풀어준다. 거듭제곱하는 수가 짝수이면, 반절만큼의 거듭제곱들을 서로 곱해주는 식으로, 홀수이면 반절만큼의 거듭제곱들(소수점 이하 버림 을 서로 곱해준 뒤, 한 번을 더 곱해주는 식으로 분할한다. 결국 1에 도달했을 때는, 그 숫자를 return 함과 동시에 모듈러 연산을 고려하여 정답을 도출해낸다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
using namespace std;
long long func(int x, int y, int z){
if(y==1){
return x;
}
else{
long long result = func(x, y/2, z);
if(y%2 == 0){
return (result%z*result%z)%z;
}
else{
return (((result*result)%z)*x)%z;
}
}
}
int main(){
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
printf("%lld\n", func(a%c, b, c));
}
