oVeron

소수와 짝수 세미소수의 합으로 \(N\)을 몇 개나 나타낼 수 있는지 묻는 문제이다.먼저 에라토스테네스의 체를 이용해 \(NloglogN\)으로 소수와 짝수 세미소수를 구한다.다음으로 소수와 짝수 세미소수를 다항식으로 나타낸다. 예를 들어 소수 5를 \(1 * x^5\)로 나타내는 식이다.그 후 두 다항식을 FFT를 이용해 곱하면, 소수와 짝수 세미소수의 합의 개수가 계수에 나타난다.#include using namespace std;typedef long long ll;typedef pair pii;typedef pair pll;typedef tuple tiii;typedef complex cd;const double PI = acos(-1);const int MAXN = 1000001;int prim..

알고리즘/baekjoon 2024. 8. 11. 13:39