공hannah부
거듭제곱 본문
거듭제곱
기본 거듭제곱
- 음이 아닌 정수 a, x와 자연수 m에 대해 a^x(mod m) ← 모듈러 취하는 이유: integer overflow 때문!
- 거듭 제곱 정의대로 a를 x번 곱하면 된다.
- 시간 복잡도: O(x)
분할정복을 이용한 거듭제곱 (더 빠른 방법)
- x가 짝수일 때 a^x = a^(x/2) * a^(x/2) 로 구하기
- x가 홀수일 때 a^x = a^(x/2) * a^(x/2) * a 로 구하기
- 시간 복잡도: O(logx)
C++로 구현
- 반복문
int m;
int fpow2(int a, int x) {
int ret = 1;
while (x) {
if (x % 2) ret = ret * a % m;
a = a * a % m;
x /= 2;
}
return ret;
}
- 재귀문
int m;
int fpow1(int a, int x) {
if (x == 0) return 1;
int ret = fpow1(a, x / 2);
ret = ret * ret % m;
if (x % 2) ret = ret * a % m;
return ret;
}
'공부 > 알고리즘' 카테고리의 다른 글
최대공약수(gcd)와 최소공배수(lcm) / 유클리드 호제법 (0) | 2023.08.03 |
---|---|
선형 자료 구조 (배열, 연결 리스트, 스택, 큐, 덱) (0) | 2023.07.31 |
비교 함수 / STL sort (0) | 2023.07.31 |
정렬 (버블정렬, 삽입정렬, 퀵정렬, 병합정렬) (0) | 2023.07.31 |
C++기초, C++ STL (0) | 2023.07.25 |