[BOJ 12792] 주작 주 주작

문제 링크 : https://www.acmicpc.net/problem/12792

문제

곧 다가올 학교 축제를 위해, 쿠사과는 참가비를 내고 여러 사람이 동시에 즐길 수 있는 게임을 만들었다. 이 게임의 알파이자 오메가는 추첨기이다. 이 추첨기는 1번부터 N번까지 둥글게 구멍이 위 아래로 하나씩 나 있고, 추첨기 윗편 구멍에 구슬을 넣으면 안에서 정해진 통로에 따라 복잡하게 움직이다가 아래 구멍 중 하나로 떨어지게 된다.

게임은 간단하다. N명이 동시에 모여 추첨기에서 1부터 N이 적힌 자리에 각각 한 명씩 선 뒤, 쿠사과가 1번 사람부터 N번 사람까지 차례로 돌아가면서 구슬을 하나씩 넣고, 어느 위치에 떨어지는지 본다. 만약 어떤 사람이 자신의 위치에서 넣은 구슬이 그대로 자신이 선 위치의 아래 구멍으로 나오게 되면 아무 일도 일어나지 않지만, 다른 자리에 떨어지면 그 사람은 경품을 얻게 된다. 단 모든 사람이 경품을 받는 경우, 즉 모든 사람이 자신이 선 위치와 다른 곳으로 구슬이 떨어지면 이 판은 잭팟이 되어 모두가 경품을 받지 못한다.

추첨기의 내부 동작에 대해 전혀 알 수 없는 사람들이 생각하기에는 그냥 웬만하면 경품을 얻는 꿀같은 게임이라고 생각하겠지만, 쿠사과의 생각은 조금 달랐다. 언듯 보기에는 구슬이 랜덤하게 떨어져 내려오는 것 같았지만 실제로는 사전에 정해진 결과대로 내려오기 때문이었다.

또한 추첨기를 처음 한 개 만드는 건 매우 어려웠지만 복제하는 것은 매우 간단했기 때문에, 추첨기에 똑같은 추첨기를 다시 연결하는 식으로 하면 겉에서 보기에는 하나의 추첨기이고 또 더 화려하게 움직이지만 내부적으로는 조작된 추첨기를 얻을 수 있다.

예를 들어 1 → 2, 2 → 1, 3 → 4, 4 → 3으로 구성된 추첨기가 있다면, 이건 이미 쿠사과가 무조건 이득을 보는 좋은 기계이다. 이 기계를 두 개 연결하게 되면 1 → 1, 2 → 2, 3 → 3, 4 → 4가 되어 아무런 일도 일어나지 않지만, 다시 한 개 더 연결하게 되면 처음처럼 쿠사과가 무조건 이득을 보는 좋은 기계가 된다.

이렇게 게임을 진행하면, 1번 사람부터 점점 다른 위치로 나와서 모두가 신나하다가, 점점 모두가 다른 위치로 나오는 것에 경악하게 될 것이다. 그리고 N번 사람의 구슬이 마지막 추첨기 밖으로 나오는 순간, 쿠사과는 "아이쿠 그런데 그것이 실제로 일어났습니다" 라고 말하며 즐거워할 생각에 가득차 있다.

쿠사과는 가급적이면 2개 이상의 추첨기를 서로 연결해 게임의 박진감을 불러일으키고자 한다. 추첨기가 주어질 때, 쿠사과가 이득을 보는 결과를 얻으려면 몇 개의 추첨기를 연결해야 할까?

입력

첫 줄에는 정수 N (1 ≤ N ≤ 1000000) 이 주어진다. 다음 줄에는 N개의 정수 J_i가 공백으로 구분되어 주어지며, 각 정수는 1에서 N 사이이며 끝을 포함한다. 이는 i번 자리에 선 사람이 얻게 되는 결과 정수를 뜻한다.

출력

추첨기를 몇 개 연속으로 연결하면 쿠사과가 이득을 보는 결과를 얻을 수 있는지 출력한다. 이 값은 2 이상 2 × 10⁹ 이하여야 하지만, 조작된 결과를 얻을 수만 있다면 어떤 값이든 상관없다. 만약 주어진 범위 안에서 조작할 방법이 없다면 -1을 출력하라.

제한

시간 제한	메모리 제한
1sec	256MB

---

풀이

$N$명의 사람이 참여하는 추첨기에서 동일한 기계를 여러 번 연결하여, 모든 사람이 자신의 처음 위치와 다른 위치로 나오게 만드는 연결 횟수 $k$를 찾는 문제다. 문제에서 말하는 ‘잭팟’ 조건은 모든 사람 $i$에 대하여 $k$번의 연결 후 결과가 자기 자신이 아니어야 함을 의미한다.

추첨기의 동작은 수학적으로 순열로 표현할 수 있으며, 모든 순열은 서로소인 사이클들의 결합으로 분해할 수 있다. 어떤 사람 $i$가 포함된 사이클의 길이를 $L$이라고 할 때, $k$번의 연결 후에 다시 제자리로 돌아올 조건은 다음과 같다.

\[k \equiv 0 \pmod L\]

즉, $k$가 해당 사이클 길이 $L$의 배수라면 그 사이클에 속한 사람들은 다시 제자리로 돌아오게 된다. 반대로 모든 사람이 제자리로 돌아오지 않으려면(잭팟이 터지려면), 모든 사이클의 길이 $L$에 대하여 $k$가 $L$의 배수가 아니어야 한다.

\[f^k(i) \neq i\]

여기서 두 가지 경우를 생각할 수 있다.

1. 길이가 $1$인 사이클이 존재하는 경우: 즉, $f(i) = i$인 사람이 한 명이라도 있다면, 어떤 $k$를 선택하더라도 $f^k(i) = i$가 되므로 잭팟을 만드는 것은 불가능하다. 이 경우 $-1$을 출력한다.
2. 모든 사이클의 길이가 $2$ 이상인 경우: 모든 사이클의 길이 $L$은 $2 \leq L \leq N$의 범위를 갖는다. 우리는 $2$부터 $N$ 사이의 어떤 수로도 나누어떨어지지 않는 $k$를 하나만 찾으면 된다.

가장 확실한 방법은 $N$보다 큰 소수를 $k$로 선택하는 것이다. 문제에서 $N$은 최대 $1\,000\,000$이므로, $1\,000\,000$보다 큰 첫 번째 소수인 $1\,000\,003$을 선택하면 정답 범위($2 \leq k \leq 2 \times 10^9$)를 만족하면서 모든 사이클 길이의 배수가 되지 않음을 보장할 수 있다.

소스코드

Github Link : Source Code

참고 알고리즘 :