두 수의 최대공약수(GCD)를 구하는 문제 중에는 한쪽 숫자가 비정상적으로 큰 경우가 있습니다. 특히 aⁿ 형태의 값은 a와 n이 각각 최대 10⁹까지 커질 수 있기 때문에, long을 포함한 일반적인 정수 자료형으로는 저장조차 할 수 없습니다.
예를 들어 a = 10248585, n = 1000000, c = 12564라면 GCD(aⁿ, c)의 결과는 9입니다. 그렇다면 실제로 aⁿ을 계산하지 않고도 이 값을 어떻게 구할 수 있을까요?
핵심 아이디어: 모듈러 지수 연산
aⁿ이 너무 크기 때문에 유클리드 호제법을 곧바로 적용할 수 없습니다. 대신 다음과 같은 수학적 성질을 활용합니다.
- GCD(aⁿ, c) = GCD(aⁿ mod c, c) — 나머지 연산을 적용해도 최대공약수는 변하지 않습니다.
- 모듈러 지수 연산(modular exponentiation)을 사용하면 aⁿ mod c를 O(log n) 시간 안에 구할 수 있습니다.
- a mod c = 0이라면 aⁿ 역시 c로 나누어 떨어지므로 답은 곧 c입니다.
즉, 거대한 aⁿ 전체를 다루는 대신 (aⁿ mod c)라는 c보다 작은 값만 계산한 뒤, 이 값과 c의 최대공약수를 구하면 됩니다.
C++ 구현 코드
#include<iostream>
#include<algorithm>
using namespace std;
long long power(long long a, long long n, long long b) {
long long res = 1;
a = a % b;
while (n > 0) {
if (n & 1)
res = (res*a) % b;
n = n>>1;
a = (a*a) % b;
}
return res;
}
long long bigGCD(long long a, long long n, long long b) {
if (a % b == 0)
return b;
long long exp_mod = power(a, n, b);
return __gcd(exp_mod, b);
}
int main() {
long long a = 10248585, n = 1000000, b = 12564;
cout << "GCD value is: " << bigGCD(a, n, b);
}실행 결과
GCD value is: 9
코드 동작 원리
power() 함수 — 빠른 거듭제곱
power() 함수는 분할 정복 기법으로 aⁿ mod b를 계산합니다. n이 홀수일 때는 결과값에 a를 곱해 저장하고, 매 반복마다 n을 절반으로 줄인 뒤 a를 제곱합니다. 이렇게 하면 n번 곱하는 대신 약 log₂n번의 곱셈만으로 연산을 마칠 수 있습니다.
bigGCD() 함수 — 최종 GCD 계산
먼저 a % b == 0인지 검사합니다. 참이라면 aⁿ도 b로 나누어떨어지므로 즉시 b를 반환합니다. 그렇지 않으면 power()로 aⁿ mod b를 구한 뒤, __gcd()를 호출해 이 값과 b의 최대공약수를 얻습니다.
시간 복잡도
전체 알고리즘의 시간 복잡도는 O(log n)입니다. aⁿ을 실제로 계산하지 않기 때문에 지수가 아무리 커져도 빠르게 정답을 구할 수 있습니다.