Discussion @ 1024. Permutations @ Timus Online Judge

WHY LCM and GCD?? Bochkaryov_Pavel 25 Oct 2006 00:19

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.

Re: WHY LCM and GCD?? jagatsastry 24 Jan 2008 01: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.

Re: WHY LCM and GCD?? Egor Stepanov [mikroz] 8 May 2008 14:37

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

Re: WHY LCM and GCD?? Vedernikoff Sergey 8 May 2008 18:21

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)

Re: WHY LCM and GCD?? Madhav 18 Jun 2008 00:38

what is this length of the cycle?Explain it please

Some explanation melkiy 2 Mar 2009 04:49

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.

Re: WHY LCM and GCD?? nehzilrz 1 Mar 2009 13:43

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

Re: WHY LCM and GCD?? SubmitRush 12 Aug 2009 13:18

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

Bochkaryov_Pavel wrote 25 October 2006 00:19

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.

Discussion of Problem 1024. Permutations