BOJ 28141 - Easy Interactive Problem

July 23, 2023

$1000$ 보다 큰 소수들을 각 소수끼리의 차이가 1000보다 크게 나열해보자.

이를 $p_i$ 라 한다.

현재 방문되지 않은 수가 $i$ 라면

$x=i,k=p_j$ 로 쿼리를 물어본다.

소수는 $2 \sim 1000$ 까지의 수로 나누어 떨어지지 않기 때문에 결과가 $i$ 가 나온다면 길이 $1$ 의 싸이클임을 알 수 있다.

그렇지 않다면 처음 쿼리 결과가 나올 때 까지 $p_j+1,p_j+2, \cdots$ 처럼 쿼리를 날려준다.

최악의 경우 $2$ 개씩 묶인 싸이클이 $N/2$ 개 존재하여 $\left\lfloor 3N/2 \right\rfloor$ 번 쿼리를 날리게 된다.

이제 싸이클을 하나 찾았다면, $i$ 가 싸이클에 있는 위치, $p_j ~ \% ~ \vert C \vert$ 의 offset 두 가지 요인을 고려하여 정답을 채워줄 수 있다.

You may also enjoy