Postată de	Clasa	Intrare/ieșire	Limită timp	Limită memorie	Sursa problemei	Autor	Dificultate
Tir Vlad Ioan (Vlad3108)	11	permutarepow.in / permutarepow.out	0.13 secunde	11 MB / 1 MB	-	Vlad Ioan Țîr	dificilă

Cerința

Fie ∆ o permutare de gradul n. Se cere să se calculeze perioada principală a funcției f(x) = ∆^x.

Date de intrare

Fișierul de intrare permutarepow.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale distincte separate prin spații, reprezentând valorile permutării ∆.

Date de ieșire

Fișierul de ieșire permutarepow.out va conține pe prima linie numărul P, reprezentând perioada principală a funcției f.

Restricții și precizări

1 ≤ n ≤ 1.000.000
Numerele de pe a doua linie vor aparține intervalului [1,n]
Despre permutări

Exemplu:

permutarepow.in

4
3 4 2 1

permutarepow.out

Explicație

$\begin{center}& \Delta& =\begin{pmatrix}& 1& &2& &3& &4& \\& 3& &4& &2& &1& \end{pmatrix},& \Delta^{2}& =\begin{pmatrix}& 1& &2& &3& &4& \\& 2& &1& &4& &3& \end{pmatrix},\newline & \Delta^{3}& =\begin{pmatrix}& 1& &2& &3& &4& \\& 4& &3& &1& &2& \end{pmatrix},& \newline& \Delta^{4}& =\begin{pmatrix}& 1& &2& &3& &4& \\& 1& &2& &3& &4& \end{pmatrix},& \Delta^{5}& =\begin{pmatrix}& 1& &2& &3& &4& \\& 3& &4& &2& &1& \end{pmatrix}& \end{center}$
Se observă că ∆ = ∆ ⁵, deci perioada principală este 4.