문제 링크
1. 아이디어
간단하게 $A^B \ (\mathrm{mod}\ C)$를 구해야 하는 문제다. $B$의 크기가 최대 $2{,}147{,}483{,}647$이어서 반복적으로 곱하는 방식으로는 $O(B)$의 시간 복잡도가 소요돼서 해결할 수 없다. $O(B)$보다 빠른 알고리즘으로 해결해야 하는데 $O(\log{B})$의 시간 복잡도로 거듭제곱을 계산할 수 있는 이진 거듭제곱이라는 테크닉을 활용하면 해결할 수 있다. 모듈러 연산은 곱셈에 대한 분배가 가능하므로 연산마다 나머지만 취했다.
2. 복잡도
| 접근 | 시간 | 공간 |
|---|
| 반복문 이진 거듭제곱 | $O(\log B)$ | $O(1)$ |
| 재귀 이진 거듭제곱 | $O(\log B)$ | $O(\log B)$ |
($B$ = 입력값 b)
3. 코드
풀이 1: 반복문 이진 거듭제곱 [Java][C++]
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
26
| import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
System.out.println(modPow(a, b, c));
}
static long modPow(long a, long b, long c) {
long res = 1;
while (b > 0) {
if ((b & 1) > 0) res = res * a % c;
a = a * a % c;
b >>= 1;
}
return res;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include <bits/stdc++.h>
using namespace std;
long long mod_pow(long long a, long long b, long long c) {
long long res = 1;
while (b > 0) {
if (b & 1) res = res * a % c;
a = a * a % c;
b >>= 1;
}
return res;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int a, b, c;
cin >> a >> b >> c;
cout << mod_pow(a, b, c);
}
|
풀이 2: 재귀 이진 거듭제곱 [Java][C++]
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
26
| import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
System.out.println(modPow(a, b, c));
}
static long modPow(long a, long b, long c) {
if (b == 0) return 1;
long half = modPow(a, b / 2, c);
if (b % 2 != 0) {
return half * half % c * a % c;
} else {
return half * half % c;
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include <bits/stdc++.h>
using namespace std;
long long mod_pow(long long a, long long b, long long c) {
if (b == 0) return 1;
long long half = mod_pow(a, b / 2, c);
if (b % 2) {
return half * half % c * a % c;
} else {
return half * half % c;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int a, b, c;
cin >> a >> b >> c;
cout << mod_pow(a, b, c);
}
|