### PROBLEM LINK:

**Author:** Dmytro Berezin

**Tester:** Shang Jingbo and Gerald Agapov

**Editorialist:** Devendra Agarwal

### DIFFICULTY:

EASY

### PREREQUISITES:

LCM of numbers.

### PROBLEM:

There are N bandits from 1 to N. Given a permuatation of 1 to N which determines that the bandit at ith position should move to jth position. At every whistle the bandit staying on position i should run to the j-th position. Now you need to find minimum number of whistle such that each bandit is at it’s original location.

### Quick Explanation

Find all independent cycle of rotation and then find the lcm of the length of each cycle.

### Explanation

Cycle here denotes the positions with which a bandit at position i moves to come to position i.

For example : 2 3 1 5 4 [ Sample Test Case 2 ]

Bandit at position 1, 2 and 3 come to their original position after every 3 whistles.

Bandit at position 4 and 5 come to their original position after every 2 whistles.

Finding lcm will give you the minimum whistle required so that every bandit is in their original position. Proof is left as an exercise for the reader to complete it.

**Challenge 1** : Finding the cycle lengths.

Cycle length can be found simply by iterating through each cycle.Please have a look at pseudo code for more insights.

**Pseudo Code**

```
Let Visited[] be 0 initialized.
Matching[] is the initial given array.
for(int i=1;i<=N;i++)
if( Visited[i]==0 )
length =1,s=Matching[i];
Visited[i]=1;
//iterating the cycle
while( s != i )
Visited[s]=1;
length++;
s= Matching[s];
```

**Challenge 2** : Finding the lcm of the lengths.

Since this can be very large number , you need to be extremely careful in many languages about this because of the size limit of the data types.

So , for every length of the cycle we got , we need to separate it in terms of prime numbers alone i.e. length = p_{1}^e_{1} * p_{2}^e_{2} *…* p_{k}^e_{k} , where p_{i} is prime number and e_{i} is the maximum power of each prime number.

We need to maintain a global array of prime numbers in which we will keep the maximum value of power of every prime numbers.From this step we are finding lcm. Finally , when we have got the array , we will find the lcm by multiplying every prime number raised to it’s maximum power modulo given_mod.

For Example:

let the given array be

2 3 4 1 6 7 5 9 10 11 12 8 14 13

Cycle 1 : 2 3 4 1

Cycle 2 : 6 7 5

Cycle 3 : 9 10 11 12 8

Cycle 4 : 14 13

Length of Cycles are : 4,3,5 and 2

Max_Power_Of 2 is 2

Max_Power_Of 3 is 1

Max_Power_Of 5 is 1

So the Answer is 2^{2} * 3^{1} * 5^{1} = 60

**I will urge the readers to figure out the error in the given pseudo code below :**

```
Wrong_Solution ( Length L[] ) //given array of lengths
ans = 1
for ( i = 1 ; i<=L.size() ; i = i+1 )
ans = lcm ( ans,L[i] )
if ans >= mod :
ans %= mod
```

**Complexity**:

O(N) , you just need to find cycles in O(N) time and factorization is done in sqrt(N) time.

### AUTHOR’S and TESTER’S SOLUTIONS:

Author’s solution to be uploaded soon.

Tester’s solution