[19060] Secret Permutation

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

19060번: Secret Permutation

 

$a_i,b_i,c_i$를 쿼리로 넣으면 $p^{-1} (p (a_i) \cdot p (b_i) + p (c_i))$의 값을 출력해준다고 했을 때 $12\,512$번 이내로 쿼리를 수행해 순열 하나를 찾는 문제입니다.

 

$p^{-1} (p (a_i) \cdot p (b_i) + p (c_i))$에서 $p (a_i)$값 $p (b_i)$ 값 그리고 $p (c_i)$ 세개 모두 모르는 상태이고 이 상태로는 $p(x)=k$를 만족시키는 특정한 값 $x$를 찾는게 어렵습니다. 하지만 몇가지 관찰을 이용하면 몇가지 수에 대해서는 값을 구하는게 가능합니다.

 

우선 $?\;0\;0\;0$ 쿼리를 넣었다고 가정해봅시다. 그러면

 

$p^{-1} (p (0) \cdot p (0) + p (0)) = p^{-1} (p (0) \cdot (p (0) + 1)) $

 

의을 알아낼 수 있습니다. 이 값을 $k_0$라고 하겠습니다. 이제 $k_0$를 쿼리할 때 넣어준다면 $p(k_0)$가 들어가므로 $p(0) \cdot (p(0)+1)$를 넣는 것과 같은 효과를 낼 수 있습니다.

 

이번에는 $?\;k_0\;1\;k_0$를 넣어본다면 

 

$p^{-1} (p (k_0) \cdot p (1) + p (k_0)) = p^{-1} (p (k_0) \cdot (p (1) + 1)) $

 

를 얻을 수가 있습니다. 이 과정을 $n$번 반복해본다면 결국 $p^{-1}(p(0) \cdot \Pi_{i=0}^{n-1} (p(i)+1))$를 얻을 수 있는데, $0$에서 $n-1$까지 모든 $p(i)+1$를 곱했기 때문에 반드시 하나는 $n$이므로 $n$으로 나눴을 때 값이 0이 됩니다. 따라서 저 식의 결과는 항상 $p^{-1}(0)$이 되게 됩니다. 최대 $5\,000$의 쿼리를 통해서 $0$이 들어있는 위치를 알아낼 수 있습니다!

 

이제 본격적으로 순열을 구해봅시다. 어느 정도 관찰을 해본다면 $n$과 서로소인 값의 위치를 하나 알아낸다면 문제를 풀어낼 수 있다는 사실을 알게 됩니다. 왜냐하면 $n$과 서로소인 어떤 수 $a$에 대해서 $a^{\phi(n)}=1$이 법 $n$에 대해서 항상 성립하며, 이를 이용해서 $1$이 들어 있는 위치를 찾아냈다면 $1 \cdot 1+1=2$ 이므로 $2$의 위치를 구하고, $1 \cdot 2 +1 =3$이므로 $3$의 위치를 구하고... 이걸 반복해서 $0$에서 $n-1$까지 모든 수들이 들어 있는 위치를 구할 수가 있게되기 때문입니다.

 

특정한 서로소를 찾아내는건 어렵지만 어떤 값을 서로소라고 가정하고 $\phi(n)$번 곱해서 1이 되는지를 확인해보면 값은 몰라도 1은 얻어낼 수 있기 때문에 꽤 간단해집니다. 앞서 구한 $0$의 위치를 $c_i$에 넣는다면 식은 두 수의 곱만 확인하는 걸로 변하므로 이걸 이용해서 거듭제곱을 사용하면 $\log(\phi(n))$의 횟수로 곱셈을 할 수가 있습니다. 이걸 이용해서 $\phi(n)$번 곱해보고 아무 수나 10개 정도 가져와서 결과값이 정말 $1$이 맞았는지를 확인해보는걸 반복하다보면(임의의 수 $x$에 대해서 $p^{-1}(1 \cdot x + 0)$의 값은 항상 $x$가 되어야 합니다. 만약 $x$가 나오지 않았다면 $1$이 아니였다는 뜻이므로 다른 수를 집어 위의 과정을 다시 해주면 됩니다.) $1$의 위치를 얻어낼 수가 있습니다. $1$을 찾아냈으니 위에서 말한 것 처럼 $0$에서 $n-1$까지 모든 수들의 위치를 구할 수가 있으므로 답을 찾을 수가 있습니다.

 

횟수를 구해봅시다. 맨 처음에 0을 구하는 과정과 1을 구하고 모든 수들의 위치를 찾는 과정은 둘 다 최대 5000번이 걸리므로 10000번의 횟수가 필요합니다. 그렇다면 1을 찾아내는 과정은 2000번 이내로 할 수 있어야합니다. $\log(\phi(n))$은 $10$번보다 적고, $1$인지 확인해보는 것도 수를 $10~20$개 정도만 사용하기 때문에 넉넉하게 잡아서 임의로 한 수를 골라서 해당 수를 통해서 $1$을 만들어 보는 과정을 $50$번에 한다고 놓아봅시다. 만약 골랐던 수가 $n$과 서로소가 아니라 $1$로 만드는데 실패했다면 다른 수를 골라 같은 방법으로 $50$번의 연산을 사용해서 $1$을 만드는 과정을 반복하게 될 것입니다. 그렇다면 $2000/50=40$이므로 수를 40개 정도 확인할 수 있게 됩니다.

 

$5000$ 이하의 수 $n$에 대해서 임의로 수 하나를 골랐을 때 그 값이 $n$과 서로소일 확률은 적어도 $20%$ 정도이므로 40번 시도해서 $n$과 서로소인 수를 적어도 하나 찾아서 1을 만드는데 성공할 확률은 $100 \cdot (1-(\frac{4}{5})^{40})$입니다. 이 값은 $99.98670772004215084127096192939719655424...$이므로 거의 높은 확률로 40번 이내에 성공함을 보일 수 있습니다. 따라서 확률론적으로 꽤 괜찮은 풀이가 됩니다.

 

이 문제는 결정론적 풀이도 존재한다고는 하지만... 저는 잘 모르겠습니다.