백준 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$차 항의 계수만 ..
백준 5051번 피타고라스의 정리
N이 주어졌을 때, 아래를 만족하는 $(a,b,c)$쌍의 개수를 찾는 것이 목표입니다. $$ 0 \lt a,b,c \lt N, \quad a \le b, \quad a^2 + b^2 \equiv c^2 \pmod N $$ N이 최대 500,000이기 때문에 나이브하게 구하면 시간초과가 납니다. 위에서 요구하고 있는 식을 잘 보면 결국 두 수의 합이 특정 수가 되는 경우의 수를 원하는 것입니다. 생성함수를 이용해 접근합시다. 다음과 같은 다항식을 생각합시다. $$ f(x) = \sum_{i=0}^{N-1}a_ix^i, \quad a_i = \vert S_i \vert \quad where \quad S_i=\{x \vert x^2 \equiv i \pmod N, 0 \lt x \lt N\} $$ 이제 이렇..
백준 11714번 Midpoint
문제 요약 2차원 평면 상에서 점 $ L+M+N $개가 주어지는데, 처음 점 $L$개 $A_1,...,A_L$는 직선 $\ell_A$에 놓여있고, 그 다음 $M$개 $B_1,...,B_M$개는 직선 $\ell_B$에 놓여있고, 그 다음 N개 $C_1,...,C_N$개는 직선 $\ell_C$에 놓여있다. 이 때, $A_i$와 $B_j$의 중점이 $C_k$가 되는 $(i,j,k)$쌍의 개수를 구하는 것이 문제에서 요구하는 것이다. 중요한 사항은 같은 점들이 여러개 입력될 수 있다는 점과 각 점의 좌표는 정수이며 절댓값이 $10^5$이하 라는 것이다. 풀이 일단 $\ell_A, \ell_B$의 식을 구하는 것이 가능하니 수식으로 접근을 해보자. 직선의 방정식은 아래와 같이 놓을 수 있다. $$ \begin{a..
