이 문제에서는 각각 숫자 N을 포함하는 Q개의 쿼리가 주어집니다. 우리의 과제는 C++를 사용하여 1부터 N까지의 순서 없는(unordered) 서로소 쌍의 개수를 세는 프로그램을 작성하는 것입니다.
서로소(Co-prime)는 흔히 '상호 소수(relatively prime)' 또는 '상호 짝수(mutually prime)'라고도 불리며, 두 수 사이에 공약수가 오직 1뿐인 수의 쌍을 의미합니다.
문제 이해를 위한 예시
입력: Q = 3, queries = [5, 7, 9]
출력: 10, 18, 28
설명
N = 5일 때 서로소 쌍은 다음과 같습니다.
(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 5), (3, 4), (3, 5), (4, 5)
총 10개의 쌍이 존재하므로 첫 번째 쿼리의 답은 10입니다.
해결 접근 방법
이 문제에 가장 효과적인 해결책은 오일러 피 함수(Euler's Totient Function), 즉 φ(N)을 활용하는 것입니다. φ(N)은 1부터 주어진 값 N까지의 자연수 중 N과 서로소인 수의 개수를 계산합니다.
오일러 피 함수는 다음과 같이 정의됩니다.
$$𝛷(𝑁) = 𝑁 ∏_{𝑝|𝑁} (1 − 1/𝑝)$$
여기서 p는 N의 모든 소인수(prime factor)를 나타냅니다.
핵심 아이디어는 다음과 같습니다.
1단계: 에라토스테네스의 체와 유사한 방식으로 1부터 N까지의 모든 값에 대해 φ(i)를 미리 계산합니다.
2단계: 누적합을 이용해 CoPrimePairs[i] = CoPrimePairs[i-1] + φ(i) 형태로 1부터 i까지의 서로소 쌍 개수를 저장한 배열을 만듭니다.
3단계: 각 쿼리가 들어올 때마다 미리 계산된 배열에서 값을 바로 조회(O(1))하여 반환합니다.
이렇게 하면 여러 개의 쿼리를 처리할 때마다 매번 계산할 필요가 없어 전체 처리 속도가 크게 향상됩니다.
C++ 구현 예제
#include <iostream>
using namespace std;
#define N 10001
int phi[N];
int CoPrimePairs[N];
void computePhi(){
for (int i = 1; i < N; i++)
phi[i] = i;
for (int p = 2; p < N; p++) {
if (phi[p] == p) {
phi[p] = p - 1;
for (int i = 2 * p; i < N; i += p) {
phi[i] = (phi[i] / p) * (p - 1);
}
}
}
}
void findCoPrimes() {
computePhi();
for (int i = 1; i < N; i++)
CoPrimePairs[i] = CoPrimePairs[i - 1] + phi[i];
}
int main() {
findCoPrimes();
int Q = 3;
int query[] = { 5, 7, 9};
for (int i = 0; i < Q; i++)
cout<<"For Query "<<(i+1)<<": Number of prime pairs is "<<CoPrimePairs[query[i]]<<endl;
return 0;
}실행 결과
For Query 1: Number of prime pairs is 10 For Query 2: Number of prime pairs is 18 For Query 3: Number of prime pairs is 28
코드 설명 및 시간 복잡도
computePhi() 함수는 체(sieve) 기법으로 φ 값을 계산합니다. 어떤 수 p가 자기 자신을 값으로 가지고 있다면(p가 소수라는 의미) p-1로 설정하고, p의 배수들에 대해서는 (phi[i]/p)*(p-1) 공식을 적용해 값을 갱신합니다.
findCoPrimes() 함수는 이렇게 구한 φ 값들의 누적합을 통해 1부터 i까지의 서로소 쌍 개수 배열을 완성합니다.
- 전처리 시간 복잡도: O(N log log N) — 체 방식의 φ 계산
- 쿼리당 시간 복잡도: O(1) — 배열 조회만 수행
- 공간 복잡도: O(N) — phi 배열과 CoPrimePairs 배열 저장
이처럼 전처리를 한 번만 수행하면 이후 몇백, 몇천 개의 쿼리가 들어와도 즉시 답을 얻을 수 있어, 반복 쿼리 문제에서 매우 효율적인 패턴입니다.