[17105] 골드바흐 트리플

%2020. 6. 13 01:07에 작성된 글입니다%

https://www.acmicpc.net/problem/17105

17105번: 골드바흐 트리플

입력으로 들어오는 홀수는 \(N\)이고

큰 소수 \(p\)에 대해 다항함수 \( f, g, h \)를

\( f\left(x\right)=x^2+x^3+x^5+...+x^p\)

\(g\left(x\right)=x^4+x^6+x^{10}+...+x^{2p}\)

\( h\left(x\right)=x^6+x^9+x^{15}+...+x^{3p} \)
라고 정의하자. 또,

모두 합해서 \(N\)이 되는 세 소수의 순서쌍 중에서

세 수가 서로 다른 수인 쌍, 두 수가 서로 같은 수인 쌍, 세 수가 전부 같은 쌍을 각각 \( t_1,\ t_2,\ t_3 \)이라고 하자.

최종 목표는 \( t_1 + t_2 + t_3 \)이고, \(f\)와 \(g\)와 \(h\)를 잘 조합하면 이걸 구할 수 있는데

\( \left\{f\left(x\right)\right\}^3,\ f\left(x\right)g\left(x\right),\ h\left(x\right) \)
에서 \( x^n \)의 계수가 \( t_1,\ t_2,\ t_3 \)에 대해 어떻게 표현되는지 보면 그대로 fft 박아서 답을 구할 수 있다.