페르마의 크리스마스 정리

• 페르마의 두 제곱수 정리 (=페르마의 크리스마스 정리)를 알아야 풀수 있는 문제인데, 다행히도 문제에 정리의 내용이 주어진다.
• 따라서 그냥 시키는대로 구현하면 된다. 범위 안의 소수들의 갯수를 세고, 소수들 중에서 4k+1 형태의 소수의 갯수를 세면 된다.
  • 2도 제곱수의 합으로 표현되는 소수임을 까먹지 말자
• 에라토스테네스의 체를 이용해서 소수 목록과 4k+1 형태의 소수 목록을 한번 구해놓고 나면, 각 쿼리에 대해서는 이분탐색을 써서 갯수를 찾아줄수 있다. 소수 목록을 구하는 데에 O(nloglogn)가 걸리고, 각 쿼리마다 O(n/logn)개의 소수들을 이분탐색 해야하므로 O(log(n/logn)) = O(logn)이 걸린다. 총 O(nloglogn + Qlogn)

"""Solution code for "BOJ 4913. 페르마의 크리스마스 정리".

- Problem link: https://www.acmicpc.net/problem/4913
- Solution link: http://www.teferi.net/ps/problems/boj/4913

Tags: [number theory]
"""

import bisect
import sys
from teflib import numtheory


def main():
    L_and_U = [[int(x) for x in line.split()] for line in sys.stdin]

    max_u = max(u for l, u in L_and_U)
    primes = numtheory.prime_list(max_u)
    square_sum_primes = [2] + [p for p in primes if p % 4 == 1]
    for l, u in L_and_U:
        if l == u == -1:
            break
        prime_count = bisect.bisect_right(primes, u) - bisect.bisect_left(
            primes, l
        )
        square_sum_prime_count = (
            bisect.bisect_right(square_sum_primes, u)
        ) - bisect.bisect_left(square_sum_primes, l)

        print(l, u, prime_count, square_sum_prime_count)


if __name__ == '__main__':
    main()

• Dependency: teflib.numtheory.prime_list