백준 17104번 골드바흐 파티션 2

짝수 N이 주어졌을 때, N을 두 소수의 합으로 나타내는 경우를 찾는 문제입니다.

N이 최대 1,000,000입니다.

소수차 항의 계수가 1이고 나머지 항의 계수는 0인 1,000,000차 다항식을 만들고 FFT를 통해 이 다항식의 제곱을 구해서 해결하는 방법을 생각해 볼 수 있습니다.

그러나, 시간제한이 0.5초로 빡빡하여 이 방법이 불가능합니다.

조금 바꿔서 생각을 해보죠. 홀수 소수 $p,q$는 $p = 2a+1, q = 2b+1$로 나타낼 수 있습니다.

$p+q=N$이라면, $N=2k=2(a+b+1)$이 됩니다. 따라서, N을 입력받았을 때 $k-1=a+b$가 되는 경우를 세면 우리가 원하는 답이 됩니다. 즉, 모든 소수 1,000,000 이하의 소수 p에 대해서 $(p-1)/2$차 항의 계수만 1이고 나머지는 0인 500,000차 다항식을 만들어서 제곱을 취해주면 됩니다.

$N=4$일 때만 짝수 소수의 합으로 나타낼 수 있으므로 이는 예외로 처리하고 나머지는 제곱의 계수를 2로 나눠서 출력하면 됩니다.

#include<bits/stdc++.h>
using namespace std;
#define MAXN 1000000
typedef complex<double> cdbl;
bool chk[MAXN+5];
vector<int> primes;
void sieve() {
    for(int i=2;i<=MAXN;++i) {
        if(!chk[i]) {
            for(int j=i+i;j<=MAXN;j+=i) chk[j] = true;
        }
    }
    for(int i=3;i<=MAXN;++i) {
        if(!chk[i]) primes.push_back(i);
    }
}

void fft(vector<cdbl> &a, bool inv) {
    int n = a.size();
    // bit reversal
    for(int i=1,j=0;i<n;++i) {
        int bit = n>>1;
        while(!((j^=bit) & bit)) bit >>=1;
        if(i<j) swap(a[i],a[j]);
    }
    for(int i=1;i<n;i<<=1) {
        double x = inv? M_PI / i : -M_PI / i;
        cdbl w = cdbl(cos(x),sin(x));
        for(int j=0;j<n;j += i<<1) {
            cdbl p = cdbl(1,0);
            for(int k=0;k<i;++k) {
                cdbl tmp = a[i+j+k] * p;
                a[i+j+k] = a[j+k] - tmp;
                a[j+k] += tmp;
                p *= w;
            }
        }
    }
    if(inv) {
        for(int i=0;i<n;++i) a[i] /= n;
    }
}

void multiply(vector<cdbl> &f, vector<cdbl> &g, vector<cdbl> &h) {
    fft(f,false); fft(g,false);
    for(int i=0;i<f.size();++i) h[i] = f[i] * g[i];
    fft(h,true);
}

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    int T; cin >> T;
    sieve();
    vector<cdbl> f(1<<20), g(1<<20), ans(1<<20);
    for(auto p:primes) {
        f[(p-1)/2] = g[(p-1)/2] = cdbl(1,0);
    }
    multiply(f,g,ans);
    while(T--) {
        int n; cin >> n;
        if(n == 4) cout << 1 << '\n';
        else cout << ceil((round(ans[n/2-1].real())/2)) << '\n';
    }
    return 0;
}