서로소 격자

이 풀이에서는 격자의 행과 열을 $0$-indexed로 생각한다. 즉 행 번호는 $0,1,2,3,4$이고, 열 번호는 $0,1,\cdots,2N-1$이다.

먼저 에라토스테네스의 체로 $2\max N_i$ 이하의 소수를 모두 구한다. 각 $N$에 대해 $2N=p+q$를 만족하는 두 소수 $p,q$를 잡는다. $p\leq q$라고 하자. 구현에서는 $N$에 가까운 소수부터 확인하면 빠르게 찾을 수 있다. 이 문제의 제한에서는 필요한 모든 $N$에 대해 이러한 소수쌍을 찾을 수 있다.

핵심은 격자를 왼쪽 $p$개의 열과 오른쪽 $q$개의 열로 나누는 것이다. 우선 일반적인 경우, 즉 $p<q$이고 $p\notin\{3,5,7\}$인 경우를 보자. 처음에는 다음과 같이 배열한다.

$$A_{r,c}= \begin{cases} 1+c+rp & (0\leq c<p),\\ 6p-c+(5-r)q & (p\leq c<p+q). \end{cases}$$

왼쪽 블록은 $1,2,\cdots,5p$를 사용하고, 오른쪽 블록은 $5p+1,5p+2,\cdots,5p+5q$를 사용하므로 전체적으로 $1,2,\cdots,10N$의 순열이다.

왼쪽 블록에서 가로로 이웃한 두 수는 항상 $1$ 차이가 난다. 따라서 모두 서로소이다. 세로로 이웃한 두 수는 정확히 $p$ 차이가 난다. 두 수의 최대공약수가 $1$보다 크다면 그 최대공약수는 $p$의 약수여야 하므로, 실제로 문제가 되는 것은 두 수가 모두 $p$의 배수인 열뿐이다. 왼쪽 블록에서는 마지막 열 $c=p-1$에

$$p,\ 2p,\ 3p,\ 4p,\ 5p$$

가 세로로 놓이므로 이 열만 고치면 된다.

오른쪽 블록도 비슷하다. 오른쪽 블록에서 가로로 이웃한 두 수는 $1$ 차이가 나므로 모두 서로소이다. 세로로 이웃한 두 수는 정확히 $q$ 차이가 난다. 따라서 오른쪽 블록에서 문제가 될 수 있는 곳은 $q$의 배수들이 한 열에 모이는 곳뿐이다.

이제 두 문제 열을 각각 고치자.

먼저 왼쪽 블록의 $p$의 배수 열을 고친다. 원래 $A_{0,1}=2$, $A_{0,3}=4$, $A_{1,p-1}=2p$, $A_{3,p-1}=4p$이다. 이 네 값을 다음과 같이 교환한다.

$$A_{0,1}=2p,\quad A_{0,3}=4p,\quad A_{1,p-1}=2,\quad A_{3,p-1}=4.$$

그러면 마지막 열은

$$p,\ 2,\ 3p,\ 4,\ 5p$$

가 된다. 인접한 두 수는 각각 $(p,2)$, $(2,3p)$, $(3p,4)$, $(4,5p)$이고, $p$는 홀수 소수이므로 모두 서로소이다.

이 교환으로 영향을 받은 다른 간선도 확인해야 한다. $2p$는 $1$과 $3$ 사이에 놓이고, 아래에는 $p+2$가 있다. $p\notin\{2,3\}$이므로 이웃한 수들과 모두 서로소이다. $4p$도 마찬가지로 $3$과 $5$ 사이에 놓이고 아래에는 $p+4$가 있으며, $p\notin\{2,5\}$이므로 문제가 생기지 않는다. 마지막 열에 들어간 $2,4$ 역시 양옆 또는 위아래의 수들이 모두 홀수이거나 $p$의 배수가 아닌 형태라서 서로소 조건을 만족한다.

이제 오른쪽 블록의 $q$의 배수 열을 찾는다. $k=\left\lfloor\frac{5p}{q}\right\rfloor$라 하자. 또한

$$l=6p-kq$$

라 하자. 그러면 오른쪽 블록의 $l$번 열에 $q$의 배수들이 모인다. 실제로 $l=p+(5p-kq)$이고, 이 열의 값은 위에서부터

$$(k+5)q,\ (k+4)q,\ (k+3)q,\ (k+2)q,\ (k+1)q$$

이다.

$k$가 짝수이면 다음과 같이 고친다.

$$A_{0,k}=(k+1)q,\quad A_{0,k+2}=(k+3)q,\quad A_{0,k+4}=(k+5)q,$$ $$A_{0,l}=k+5,\quad A_{2,l}=k+3,\quad A_{4,l}=k+1.$$

즉 $q$의 홀수 번째 배수들을 맨 위 행의 작은 수들과 교환한다. 그러면 $l$번 열은

$$k+5,\ (k+4)q,\ k+3,\ (k+2)q,\ k+1$$

꼴이 된다. 이웃한 두 수를 보면 작은 수와 $q$의 배수가 번갈아 나오며, 작은 수들은 각각 이웃한 계수와 서로소이고 $q$보다 작다. 따라서 이 열의 세로 인접쌍은 모두 서로소이다.

$k$가 홀수이면 다음과 같이 고친다.

$$A_{0,k+1}=(k+2)q,\quad A_{0,k+3}=(k+4)q,$$ $$A_{1,l}=k+4,\quad A_{3,l}=k+2.$$

이 경우 $l$번 열은

$$(k+5)q,\ k+4,\ (k+3)q,\ k+2,\ (k+1)q$$

꼴이 된다. 역시 작은 수와 $q$의 배수가 번갈아 나오므로 세로 인접쌍이 모두 서로소가 된다.

방금 옮긴 $q$의 배수들은 맨 위 행의 작은 열에 놓인다. 그 양옆의 수들은 연속된 작은 수이고, 아래쪽 수는 $p+c+1$ 꼴이다. $p\notin\{3,5,7\}$인 일반 경우에는 여기서도 공통 약수가 생기지 않는다. $p=3,5,7$을 따로 처리하는 이유가 바로 이 부분에서 작은 소수와 충돌할 수 있기 때문이다.

두 블록의 경계도 확인해야 한다. 경계에서 $r$번 행의 두 값은

$$(r+1)p,\quad 5p+(5-r)q$$

이다. 이 두 수가 공통 소인수를 가진다고 하자. 그 소인수가 $p$라면 $p$가 $(5-r)q$를 나누어야 하는데, $p\neq q$이고 $1\leq 5-r\leq 5<p$이므로 불가능하다. 그 소인수가 $r+1$의 약수라면 가능한 작은 소수는 $2,3,5$뿐이다. $2$는 오른쪽 값의 홀짝성 때문에 불가능하고, $3$ 또는 $5$가 문제가 되는 경우는 $p=3,5$ 등의 작은 경우로 따로 처리한다. 따라서 일반 경우의 경계도 모두 좋다.

이제 예외를 처리한다.

만약 $2N-1$이 소수라면 $q=2N-1$로 두고, 큰 블록의 폭을 $q$, 작은 블록의 폭을 $1$로 둔다. 다음과 같이 배열한다.

$$A_{r,c}= \begin{cases} 6+c+rq & (0\leq c<q),\\ 5-r & (c=q). \end{cases}$$

그러면 $q-6$번 열에

$$q,\ 2q,\ 3q,\ 4q,\ 5q$$

가 모인다. 여기서 $A_{1,q-6}$과 $A_{1,q}$를 교환하고, $A_{3,q-6}$과 $A_{3,q}$를 교환하면 이 열은

$$q,\ 4,\ 3q,\ 2,\ 5q$$

가 되어 세로 인접쌍이 모두 서로소가 된다. 나머지 새로 생긴 인접쌍은 작은 수 $2,4$ 또는 $2q,4q$ 주변만 확인하면 되고, 모두 서로소이다.

$p=q$인 경우에는 오른쪽 블록의 모양을 조금 다르게 잡는다. 처음 배열은 다음과 같다.

$$A_{r,c}= \begin{cases} 1+c+rp & (0\leq c<p),\\ (8-r)p+c+1 & (p\leq c<2p). \end{cases}$$

이 경우에도 가로 간선은 대부분 자동으로 좋고, 문제가 되는 곳은 $p$의 배수들이 모이는 열들뿐이다. 구현에서는 $7p,9p$와 작은 수 $7,9$를 먼저 교환하여 오른쪽의 배수 열을 분리한다. 이후 $p\bmod 3$에 따라 왼쪽 마지막 열을 고친다. $p\bmod 3=1$이면 일반 경우와 같이 $2p,4p$를 위쪽 행으로 옮기고 $2,4$를 마지막 열에 넣는다. 그렇지 않으면 $p,3p,5p$를 위쪽 행으로 옮기고 $1,3,5$를 마지막 열에 넣는다. 각 경우에서 영향을 받는 간선은 상수 개뿐이며, 직접 최대공약수를 확인하면 모두 서로소이다.

$p=3,5,7$인 경우에는 위의 일반 보정에서 작은 소수와 충돌할 수 있으므로 별도의 작은 블록을 사용한다. 작은 블록은 각각 $5\times p$ 크기이며 $1,2,\cdots,5p$를 담는다. 큰 $q$폭 블록에는 $5p+1$부터 $5p+5q$까지를 규칙적으로 배치한다. 작은 블록 내부와 경계는 미리 좋은 쌍만 생기도록 만들어 두고, 큰 블록에서 $q$의 배수들이 모이는 열만 몇 번의 교환으로 보정한다. 이 방식은 $p=3,5,7$에서만 필요하므로 배열을 코드에 그대로 넣어도 충분하다.

마지막으로 $N=1,2,3,5$처럼 아주 작은 값은 공간이 좁아 일반식의 열 인덱스가 성립하지 않을 수 있다. 이런 경우는 직접 만든 배열을 출력한다. 각 배열의 크기는 매우 작으므로, 순열 조건과 모든 인접쌍의 서로소 여부를 직접 확인할 수 있다.

전체 알고리즘은 다음과 같다.

• 모든 입력을 읽고 $\max N_i$를 구한다.
• 에라토스테네스의 체로 $2\max N_i$ 이하의 소수를 구한다.
• 각 $N_i$에 대해 위의 경우 중 하나를 적용하여 격자를 만든다.
• 만든 격자를 출력한다.

체의 시간 복잡도는 $O(M\log\log M)$이다. 여기서 $M=2\max N_i$이다. 각 격자를 출력하는 데 걸리는 시간은 격자 크기에 비례하므로 전체 출력 시간은 $O\left(\sum_i N_i\right)$이다. 메모리 사용량은 소수 배열과 한 테스트케이스의 격자를 저장하는 데 필요한 $O(\max N_i)$이다.

이 구성은 모든 인접쌍을 좋은 쌍으로 만들므로 모든 테스트케이스에서 $B_i=0$을 달성한다. 따라서 가능한 최대 점수를 얻는다.

Solution written by GPT5.5