[Python] 4913번 페르마의 크리스마스 정리

 

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

4913번: 페르마의 크리스마스 정리

---

 

22/11/13

 

 

분명 태그 하나(에라토스테네스의 체)가 보이는 문제여서 접근을 했건만, 2번의 시간초과와 여러 번의 의문의 틀렸습니다를 받고 당황했던 문제이다.

 

요구하는 선행지식은 누적 합의 개념과 에라토스테네스의 체이다.

---

 

문제 접근 방식:

 

 

먼저, 구간 내의 소수를 판정해야되고, $L$과 $U$의 범위가 최대 $1,000,000$까지 이므로, 에라토스테네스의 체를 적용해야겠다고 생각했다.

 

그래서 $1,000,000$개 짜리 배열 sieve을 선언하여 에라토스테네스의 체를 진행했다.

 

또한, 소수 중 $4c+1$의 형태를 띤 소수를 알아내야 하므로 같은 크기의 배열 sieve_2를 선언하여, 에라토스테네스의 체를 진행하는 과정에서 만약 4로 나눈 나머지가 1이라면 그 배열에 1로 선언하도록 했다.

 

그렇게 했더니 시간 초과를 받았다.

 

알고 보니, 각 쿼리마다 요구하는 범위가 넓다면 시간 초과를 받는 알고리즘이었다.

 

때문에, 이를 참고하여 누적 합 알고리즘으로 바꾸어서 에라토스테네스의 체를 변환했는데 자꾸 틀렸습니다를 받았다.

 

틀린 이유는 크게 두 가지가 있었다.

 

첫번째로, $L$과 $U$의 범위가 음수까지도 허용이 되어서 음수 소수도 허용을 하도록 했었다는 점이었다.

 

문제에서 요구하는 바는 음수 소수를 허용하지 않는 요구였다.

 

두 번째로, 위에서 $4c+1$의 형태를 띤 소수를 알아내는 과정이 잘못되었었다는 점이었다.

 

이러한 형태를 띤 소수는 백만 이하까지 범위가 있는데, 에라토스테네스의 체 과정에서 이를 판단해버린다면 1000까지 밖에 찾아낼 수가 없다.

 

이러한 두 가지 이유 때문에 틀렸었다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 4913번 페르마의 크리스마스 정리
# 수학, 소수 판정, 정수론, 에테체, 누적 합

# 전처리 구간
sieve = [1 for _ in range(1000001)]
sieve_2 = [0 for _ in range(1000001)]
sieve[0], sieve[1] = 0, 0
for i in range(2, 1500):
    if sieve[i]:
        for j in range(2*i, 1000001, i):
            sieve[j] = 0
sieve_2[2] = 1
for i in range(3, 1000001):
    if sieve[i] and i%4 == 1:
        sieve_2[i] = 1
# 누적 합 처리
for i in range(1, 1000001):
    sieve[i] += sieve[i-1]
    sieve_2[i] += sieve_2[i-1]

# 쿼리
while True:
    L, U = map(int, input().split())
    if L == -1 and U == -1:
        break
    x, y = 0, 0
    if L >= 1:
        x = sieve[U] - sieve[L-1]
        y = sieve_2[U] - sieve_2[L-1]
        print(L, U, x, y)
    elif L < 1 and U >= 0:
        x = sieve[U]
        y = sieve_2[U]
        print(L, U, x, y)
    elif L < 1 and U < 0:
        x = 0
        y = 0
        print(L, U, x, y)