fork(2) download
copy 
  1. #include<iostream>
  2. using namespace std;
  3. int gcd(int a,int b);    //to find GCD of 2 nos
  4. int main()
  5. {
  6.     unsigned long arr1[10000]={0},arr2[10000]={0},arr3[10000]={0};
  7.     int cases,i,j,total,x,k,b=0;
  8.     cin>>cases;           //total no of test cases
  9.     for(k=0;k<cases;++k)
  10.     {
  11.     cin>>total;           // total no. of bandits
  12.     for(i=1;i<=total;++i)
  13.     {
  14.        cin>>arr1[i];       //each unique location stored in arr1 & arr2
  15.        arr3[i]=arr1[i];
  16.     }
  17.     for(i=1;i<=total;i++)  //if all are in right places, they stop after Ist whistle
  18.     {
  19.         if(arr1[i]!=i)
  20.             break;
  21.         else
  22.             b++;
  23.     }
  24.  
  25.     for(i=1,j=1;i<=total,j<=total;++i,++j)
  26.     {
  27.     while(arr1[i]!=i)     //while they're in incorrect positions
  28.     {
  29.     x=arr1[arr1[i]];      
  30.     arr1[i]=x;            //arr1[i] gets updated to arr1[arr1[i]]; Verify this by taking a case
  31.     arr2[j]++;            //I wish to calculate LCM of the values this arr2 stores
  32.     }
  33.  
  34.     arr1[i]=arr3[i];      //this resets value of arr1
  35.     }
  36.     for(i=1;i<=total;++i)
  37.     {
  38.         arr2[i]=(1+arr2[i]);//increases the value of each element by 1(as I couldn't initialize entire array with one) )
  39.     }
  40.  
  41.  
  42. unsigned long long lcm;            //simple fn to calc. lcm using GCD
  43. lcm=arr2[1]*arr2[2]/gcd(arr2[1],arr2[2]);
  44. for(i=3;i<=total;i++)
  45.                   lcm=lcm*arr2[i]/gcd(lcm,arr2[i]);
  46.  
  47. if(b==total)                       //if all in right place output 1
  48. cout<<1<<endl;
  49. else
  50. cout<<(lcm%(1000000000+7))<<endl; //o/w output modulo of the lcm
  51. lcm=0;
  52. x=0,i=0,j=0,b=0;
  53. for(i=1;i<=total;++i) //initialzing all the arrays 
  54. {
  55.     arr1[i]=0;
  56.     arr2[i]=0;
  57.     arr3[i]=0;
  58. }
  59.     }
  60. return 0;
  61. }
  62.  
  63. int gcd(int a,int b)  //GCD fn
  64. {
  65.     int rem;
  66.     if(b==0)
  67.     return a;
  68.     if(a==0)
  69.     return b;
  70.     if(b>a)
  71.     {
  72.            a=a+b;
  73.            b=a-b;
  74.            a=a-b;
  75.            }
  76.            rem=a%b;
  77.     while(rem>b)
  78.     {
  79.               a=b;
  80.               b=rem;
  81.               rem=a%b;
  82.     }
  83.               if(rem==0)
  84.               return b;
  85.               else
  86.               return rem;
  87. }
  88.  
  89.  
  90.  
Success #stdin #stdout 0s 3340KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/1Wq2aS
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!