# getting WA for SGARDEN

#include<stdio.h>

int main()
{
int t;
long long int divisor,a,dividend,lcm,n,i,length,s;
scanf("%d",&t);
while(t)
{

``````scanf("%lld",&n);
long long int visit[n+1],arr[n+1];
for(i=1;i<=n;i++)
{
scanf("%lld",&arr[i]);
visit[i]=0;
}
lcm=1;
for(i=1;i<=n;i++)
{
if(visit[i]==0)
{
length=1;
visit[i]=1;
s=arr[i];
while(i!=s)
{
visit[s]=1;
length++;
s=arr[s];
}
if(length<lcm)
{
a=lcm;
lcm=length;
length=a;
}
dividend=length;
divisor=lcm;
do
{
a=dividend%divisor;
dividend=divisor;
divisor=a;

}while(divisor!=0);
lcm=(length*lcm)/dividend;

}
}
lcm%=1000000007;
printf("%lld\n",lcm);
t--;
}
return 0;
``````

}

Go through below link and try to figure out where’s bug in your code…

http://discuss.codechef.com/questions/47240/sgarden-editorial

****Challenge 2 : Focus this part would clear your doubt i think.

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 = p1^e1 * p2^e2 … pk^ek , where pi is prime number and ei 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.
****

1 Like

is the multiplication process if overflowing? If yes, how can I control it in C++?

Thanks, but I have read the tutorial. and i am getting correct answers for all the three test cases given

but breaking such a large number into its prime factors… i mean yes we can stop at <=sqrt(num)but still…

and how will we store the result in c++? using array woulb be much complex??

One way is store all cycles in separate array… and process iteration and use %mod after every cycle…

I am sorry but I still don’t get it… thanks anyways…

@nadimayaz I followed your suggestions and wrote a new code… I have checked it for the given test cases and gone through it multiple times still I can’t find the error… But I am getting WA… Please if you can help!

http://www.codechef.com/viewsolution/4336385