개요
이 글에서는 주어진 GCD(최대공약수)와 LCM(최소공배수) 값을 동시에 만족하는 숫자 쌍의 개수를 구하는 방법을 살펴봅니다. 예를 들어 GCD가 2이고 LCM이 12라고 가정해 보겠습니다. 이 조건을 만족하는 숫자 쌍은 (2, 12), (4, 6), (6, 4), (12, 2)로 총 4가지입니다. 따라서 프로그램은 쌍의 개수인 4를 출력해야 합니다.
핵심 아이디어
두 수 a와 b의 최대공약수가 g이고 최소공배수가 l이라면 다음과 같은 성질이 성립합니다.
- l은 반드시 g로 나누어 떨어져야 합니다. 그렇지 않다면 조건을 만족하는 쌍은 존재하지 않습니다.
- a = g·x, b = g·y 형태로 나타낼 수 있으며, 이때 x와 y는 서로소(gcd(x, y) = 1) 관계입니다.
- x × y = l / g가 성립하므로, l / g의 각 소인수는 x와 y 중 정확히 하나에 온전히 배정됩니다.
따라서 temp = l / g를 계산한 뒤 temp의 서로 다른 소인수 개수를 c라고 하면, 가능한 쌍의 개수는 2^c가 됩니다. 위 예제에서 temp = 12 / 2 = 6 = 2 × 3이므로 소인수가 2개이고, 답은 2² = 4입니다.
알고리즘
countPairs(gcd, lcm):
lcm이 gcd로 나누어 떨어지지 않으면 0 반환
temp := lcm / gcd
c := temp의 서로 다른 소인수 개수
res := 1을 c번 왼쪽 시프트 (즉, 2^c)
res 반환
primeFactorCount(n): // n의 서로 다른 소인수 개수 계산
count := 0
n이 짝수이면 count를 1 증가시키고, 2로 나누어 떨어지는 동안 계속 나눔
i := 3부터 i² ≤ n까지 i를 2씩 증가시키며 반복:
n이 i로 나누어 떨어지면 count를 1 증가시키고,
i로 나누어 떨어지는 동안 n을 계속 i로 나눔
n > 2이면 count를 1 증가 (남은 소인수 처리)
count 반환
C++ 구현 예제
#include<iostream>
#include<cmath>
using namespace std;
int primeFactorCount(int);
int countPairs(int gcd, int lcm) {
if(lcm % gcd != 0) // LCM이 GCD로 나누어 떨어지지 않으면 쌍 없음
return 0;
int temp = lcm / gcd;
return (1 << primeFactorCount(temp)); // 2^(소인수 개수) 반환
}
int primeFactorCount(int n){
int count = 0;
if(n % 2 == 0){ // n이 2로 나누어 떨어지면
count++;
while(n % 2 == 0)
n = n / 2; // 소인수 2를 모두 제거
}
// 이제 n은 홀수이므로 홀수 후보만 검사하면 됨
for(int i = 3; i * i <= n; i = i + 2){
if(n % i == 0){ // n이 i로 나누어 떨어지면
count++;
while(n % i == 0)
n = n / i; // 같은 소인수가 중복 계산되지 않도록 제거
}
}
if(n > 2) // 2보다 큰 소수가 남아 있으면
count++;
return count;
}
int main() {
cout << "GCD = 2, LCM = 12일 때 가능한 쌍의 개수: " << countPairs(2, 12);
}
실행 결과
GCD = 2, LCM = 12일 때 가능한 쌍의 개수: 4
마무리
이 알고리즘은 모든 후보 쌍을 일일이 검사하지 않고 소인수 분해만으로 답을 도출하므로 매우 효율적입니다. 전체 시간 복잡도는 소인수 분해 단계의 O(√n)이 지배적이며, 여기서 n은 LCM을 GCD로 나눈 몫입니다. 참고로 이 문제에서는 (2, 12)와 (12, 2)처럼 순서가 다른 쌍도 서로 다른 것으로 계산한다는 점에 유의하세요.