백준 4913번, 페르마의 크리스마스 정리 풀이
문제 백준 4913번 풀이 구간에 해당하는 소수를 빠르게 구하기 위해서, 구간 $[1, 100,000,000]$에 해당하는 모든 소수를 에라토스테네스의 체를 사용하여 구해줍니다. 해당 구간에 소수를 순서대로 넣으면, 정렬된 상태이기 때문에 이분 탐색을 사용할 수 있습니다. 문제 입력에서 주어지는 $[L, U]$에서 $upper(U) - lower(L) $한 수가 소수의 개수가 되겠네요. 비슷하게 제곱수의 합으로 나타낼 수 있는 수도 위처럼 구할 수 있습니다. 에라토스테네스의 체로 소수($p$)를 구할 때, $(p-1)mod4 = 0$을 만족하는 경우만 따로 관리해주면서, 위처럼 이분 탐색을 사용하여 풀 수 있습니다. 다만, $1^1 + 1^1 = 2$가 되는 "짝수인 소수 2"를 따로 고려해야 합니다. ..
2020.12.26