Could you explain me why GCD and LCM are used in solution of this task? I don't understand it, and my solution without using them gets TL on test 11.

Yeah people. Can anyone please elaborate on the algorithm being used(the LCM method). Even I used the straightforward method and got TLE#11. The codes posted are of little help in making me understand the algo. Thanks in advance.

heh, the answer is LCM from lengths of cycles...

Why? This is very easy: if cycle 1 has length L1, and cycle 2 has length L2, then obviously we'll come to the initial situation after number of steps S, which should be multiple of L1 and L2, i.e. LCM of L1 and L2. Following this logic, it is straightforward that the answer to the problem is LCM (L1, L2, ..., Lp)

what is this length of the cycle?Explain it please

A*B=LCM(A,B)*GCD(A*B)

Write down how does a not long sequence behave when you apply operator P to it. Trace i-th number (number at the i-th place) and you'll see that the number has a period. This period is connected to the number of iterations needed to obtain  number i on the i-th place (why the relationship is so strong, think yourself). Since you need p[i]=i for all i, you must find LCM of all periods.

If you get WA at TEST#11,
I guess you have a problem related data overflow.
use long type.