TIL: 골드바흐 파티션(Goldbach Partition) - FFT 활용

문제 설명

골드바흐의 추측은 2보다 큰 모든 짝수는 두 소수의 합으로 표현될 수 있다는 가설이다.
이 문제에서는 주어진 짝수 N을 두 소수의 합으로 표현하는 경우의 수, 즉 골드바흐 파티션의 개수를 구해야 한다.
단, (3 + 7)과 (7 + 3)처럼 순서만 다른 경우는 같은 파티션으로 간주한다.

입력 조건

• 첫 번째 줄: 테스트 케이스의 개수 T (1 ≤ T ≤ 100,000)
• 이후 T개의 줄: 각각 짝수 N (2 < N ≤ 1,000,000)

출력 조건

• 각 테스트 케이스마다 골드바흐 파티션의 수를 출력

예제 입력

5 6 8 10 12 100

예제 출력

1 1 2 1 6

---

문제 접근 및 해결 방법

이 문제는 소수의 조합을 빠르게 구해야 한다.
소수를 두 개 더한 결과가 N이 되는 경우의 수를 효율적으로 구하기 위해 고속 푸리에 변환(FFT)을 활용한다.

핵심 아이디어

1. 에라토스테네스의 체를 사용해 1,000,000 이하의 소수를 미리 구한다.
2. FFT를 통해 소수 배열을 자기 자신과 컨볼루션(Convolution)하여 두 소수의 합으로 만들 수 있는 모든 경우를 구한다.
3. 소수의 합이 중복 계산되지 않도록 조정한다.

---

풀이 과정 및 코드 설명

1. 소수 판별 (에라토스테네스의 체)

int isNotPrime[SIZE >> 1] = {1, 1};  // 0과 1은 소수가 아님
Complex primeArray[SIZE];  // 소수를 마킹할 배열

for (long long i = 2; i < 1000000; i++) {
    if (isNotPrime[i]) continue;  // 이미 체크된 수는 넘어감
    primeArray[i] = Complex(1, 0);  // 소수를 1로 표시

    for (long long j = i * i; j < 1000000; j += i) {
        isNotPrime[j] = 1;  // 배수 제거
    }
}

• isNotPrime 배열을 통해 소수를 판별하고, 소수인 위치를 primeArray에 1로 마킹한다.

2. FFT를 이용한 소수 배열 제곱 (Convolution)

void FFT(Complex arr[], bool inverse = false) {
    int n = SIZE;
    for (int i = 1, j = 0; i < n; ++i) {
        int bit = n / 2;
        while (!((j ^= bit) & bit)) bit /= 2;
        if (i < j) swap(arr[i], arr[j]);
    }

    for (int len = 1; len < n; len *= 2) {
        double angle = (inverse ? M_PI / len : -M_PI / len);
        Complex w(cos(angle), sin(angle));
        for (int i = 0; i < n; i += len * 2) {
            Complex wp(1, 0);
            for (int j = 0; j < len; ++j) {
                Complex u = arr[i + j];
                Complex v = arr[i + j + len] * wp;
                arr[i + j] = u + v;
                arr[i + j + len] = u - v;
                wp *= w;
            }
        }
    }

    if (inverse) {
        for (int i = 0; i < n; ++i) arr[i] /= n;
    }
}

void SquareFFT(Complex arr[]) {
    FFT(arr);
    for (int i = 0; i < SIZE; i++) arr[i] *= arr[i];
    FFT(arr, true);
}

• FFT를 통해 소수 배열을 제곱하고, 역변환을 통해 두 소수의 합으로 만들 수 있는 경우를 계산한다.

3. 결과 계산 및 출력

SquareFFT(primeArray);

int testCaseCount; 
cin >> testCaseCount;

while (testCaseCount--) {
    int n; 
    cin >> n;

    int partitionCount = round(primeArray[n].real());  // 실수부에서 결과 추출
    int middlePrimeFlag = !isNotPrime[n / 2];  // n/2가 소수인지 확인

    // 중복되는 경우 조정
    if (middlePrimeFlag) partitionCount--;

    cout << partitionCount / 2 + middlePrimeFlag << "\n";
}

• primeArray[n]에서 실수부를 가져와 결과를 출력한다.
• (p + p) 형태의 중복된 소수 쌍을 조정한다.

So...

이 문제는 소수 쌍의 합을 빠르게 구해야 하므로 FFT를 활용한 Convolution 기법을 적용하였다.
기존의 완전 탐색 방식은 시간 복잡도가 높아 효율적이지 않지만,
FFT를 활용하면 (O(N \log N))의 복잡도로 문제를 해결할 수 있었다.

특히 에라토스테네스의 체와 FFT를 적절히 결합하여 대량의 쿼리도 빠르게 처리할 수 있었다.

복잡해 보일 수 있는 알고리즘이지만, 수학적 원리를 이해하고 구현하면
큰 입력도 효율적으로 해결할 수 있다는 점에서 매우 흥미로운 문제였다.