Problem:
http://codeforces.com/problemset/problem/542/C
Algorithm:
Given some x and do below for many times:
x <- f(x)
Observe the transition of x and find out that there is loop.(the shape is like "ρ")
For example, suppose n=6 and f is
f : i -> i+1 (i=1,2,3,4,5)
6 -> 3
and when x=1, then
1 -> 2 ->
3 -> 4 -> 5 -> 6 -> ...
and the loop is 3->4->5->6 -> ...
also, if we start with x=5, then
5 -> 6 -> 3 -> 4 -> ...
when x is in the loop, then x moves only in the loop. So, let k is the length of loop(in this example, k=4) and m is some multiples of k, f^m(x) moves x to x(if x is in the loop).
For x that is not in the loop will go to loop for big k. Let s is minimum number of step that is needed to go to loop for all x.(in this example, 2 steps needed to go loop and s=2), then f^(m+s)(x) moves all points to loop. and this is Idempotent.
And we must be carefull that there is some "ρ".
So, we need s to be the longest "stick" and m to be the LCM of length of loops.
