fork(1) download
  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
stdin
Standard input is empty
stdout
Standard output is empty