문제 소개
정수 N이 입력으로 주어졌을 때, 1≤A≤N과 1≤B≤N을 만족하는 모든 쌍 (A, B) 중에서 최대공약수 GCD(A, B)가 B가 되는 쌍의 개수를 구하는 것이 목표입니다. 즉, 모든 유효한 쌍에서 B가 곧 두 수의 최대공약수가 되어야 합니다.
예시를 통해 자세히 살펴보겠습니다.
입력 − N=5
출력 − gcd(A, B)가 B가 되는 (A ≤ N, B ≤ N) 쌍의 개수 − 10
설명
gcd(A, B)가 B가 되는 (A ≤ N, B ≤ N) 쌍은 다음과 같습니다 −
(1,1), (2,1), (3,1), (4,1), (5,1), (2,2), (3,3), (4,2), (4,4), (5,5)
총 10개입니다.
입력 − N=50
출력 − gcd(A, B)가 B가 되는 (A ≤ N, B ≤ N) 쌍의 개수 − 207
설명
gcd(A, B)가 B가 되는 (A ≤ N, B ≤ N) 쌍은 다음과 같습니다 :
(1,1), (2,1), (3,1), (4,1), (5,1).....(50,1)
(2,2), (3,3), (4,4).....(50,50)
마찬가지로 (4,2), (6,3), (8,2), (8,4), ...........(50,25) 같은 다른 쌍들도 포함되며, 전체 총 207개입니다.
단순 접근 방식 (Naive Approach)
주어진 문제를 해결하는 방법에는 여러 가지가 있으며, 대표적으로 단순 접근 방식과 효율적인 접근 방식이 있습니다. 먼저 단순 접근 방식부터 살펴보겠습니다.
정수 N을 입력받습니다.
함수 GCD(int A, int B)는 두 정수를 매개변수로 받아 A와 B의 최대공약수를 반환하며, 재귀적으로 gcd를 계산합니다.
A 또는 B 중 하나가 0이면 나머지 하나를 반환합니다. 두 값이 같으면 그중 하나를 반환합니다. A>B이면 GCD(A-B, B)를 호출하고, B가 더 크면 GCD(B-A, A)를 호출합니다. 이 과정을 반복하면 최종적으로 gcd 값을 얻게 됩니다.
함수 count_pairs(int N)은 N을 받아 쌍(A, B)에서 B가 gcd이고 두 값이 모두 [1, N] 범위에 속하는 쌍의 개수를 반환합니다.
쌍의 개수를 저장할 변수 count를 0으로 초기화합니다.
A에 대해 i=1부터 i=N까지 반복하는 for 루프 안에, B에 대해 j=1부터 j=N까지 반복하는 중첩 for 루프를 실행합니다.
쌍 (i, j)를 만들어 GCD(i, j)에 전달하고, 결과가 j와 같으면 count를 1 증가시킵니다.
모든 루프가 종료되면 count를 결과로 반환합니다.
이 방식의 시간 복잡도는 이중 루프와 각 gcd 계산 비용 때문에 약 O(N² log N)으로, N이 커지면 매우 느려집니다.
효율적인 접근 방식
핵심 관찰은 다음과 같습니다. gcd(a, b) = b라는 것은 a가 항상 b의 배수라는 의미입니다. 따라서 각 b(1≤b≤N)에 대해 N 이하인 b의 배수 개수, 즉 ⌊N/b⌋개의 유효한 a가 존재합니다. 결국 정답은 Σ⌊N/b⌋ (b=1~N)이 되며, ⌊N/i⌋ 값이 같은 구간을 한 번에 묶어 처리하면 O(√N) 시간에 계산할 수 있습니다.
함수 Count_pairs(int N)은 N을 받아 조건을 만족하는 쌍의 개수를 반환합니다.
쌍의 개수를 저장할 변수 count를 0으로 초기화합니다.
임시 변수 temp=N, i=1로 설정합니다.
while(i<=N) 조건 동안 다음을 반복합니다.
각 i에 대해 몫이 같아지는 구간의 끝을 j=N/temp로 계산합니다.
현재 구간에서의 쌍의 개수는 temp*(j-i+1)이며, 이를 count에 더합니다.
i=j+1로 설정하여 다음 B 값으로 넘어갑니다.
다음 반복을 위해 temp=N/i로 갱신합니다.
while 루프가 끝나면 count를 결과로 반환합니다.
예제 코드 (단순 접근 방식)
#include <iostream>
using namespace std;
// 재귀적으로 최대공약수를 계산하는 함수
int GCD(int A, int B){
if (A == 0){
return B;
}
if (B == 0){
return A;
}
if (A == B){
return A;
}
if (A > B){
return GCD(A-B, B);
}
return GCD(A, B-A);
}
// 조건을 만족하는 쌍의 개수를 세는 함수
int count_pairs(int N){
int count = 0;
for(int i=1; i<=N; i++){
for(int j = 1; j<=N; j++){
if(GCD(i, j)==j){
count++;
}
}
}
return count;
}
int main(){
int N = 4;
cout<<"gcd(A, B)가 B가 되는 (A <= N, B <= N) 쌍의 개수: "<<count_pairs(N);
return 0;
}
출력
위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −
gcd(A, B)가 B가 되는 (A <= N, B <= N) 쌍의 개수: 8
예제 코드 (효율적인 접근 방식)
#include <bits/stdc++.h>
using namespace std;
// 조건을 만족하는 쌍의 개수를 효율적으로 세는 함수
int Count_pairs(int N){
int count = 0;
int temp = N;
int i = 1;
while(i <= N){
int j = N / temp;
count += temp * (j - i + 1);
i = j + 1;
temp = N / i;
}
return count;
}
int main(){
int N = 4;
cout<<"gcd(A, B)가 B가 되는 (A <= N, B <= N) 쌍의 개수: "<<Count_pairs(N);
return 0;
}
출력
위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −
gcd(A, B)가 B가 되는 (A <= N, B <= N) 쌍의 개수: 8
마무리
N=4일 때 두 방식 모두 8이라는 동일한 결과를 출력하지만, 단순 접근 방식은 O(N² log N)의 시간이 걸리는 반면 효율적인 접근 방식은 몫 구간 묶기 기법을 활용해 O(√N)만에 답을 구할 수 있습니다. 따라서 N이 큰 경우에는 효율적인 접근 방식을 사용하는 것이 바람직합니다.