ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1024. Permutations

WHY LCM and GCD??
Posted by 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??
Posted by 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??
Posted by Egor Stepanov [mikroz] 8 May 2008 14:37
heh, the answer is LCM from lengths of cycles...
Re: WHY LCM and GCD??
Posted by 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??
Posted by Madhav 18 Jun 2008 00:38
what is this length of the cycle?Explain it please
Re: WHY LCM and GCD??
Posted by nehzilrz 1 Mar 2009 13:43
A*B=LCM(A,B)*GCD(A*B)
Some explanation
Posted by 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??
Posted by 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.