fork(1) download
copy 
  1.  
  2. #include<stdio.h>
  3. #include<math.h>
  4. long long int p[100001] = {0},i;
  5. long long int max[100001] = {0};
  6. long long int j=0;
  7. long long int factors(long long int num)
  8. {
  9. //    j=0;
  10.     long long int count[100001] = {0};
  11.     if(num%2==0)
  12.     {
  13.         p[j++] = 2;
  14.     }
  15.  
  16.     while(num%2==0)
  17.     {
  18. //        p[j++] = 2;
  19.         count[2]++;
  20.         num = num/2;
  21.     }
  22.  
  23.     for(i=3;i<=sqrt(num);i=i+2)
  24.     {
  25.         if(num%i==0)
  26.             p[j++] = i;
  27.         while(num%i==0)
  28.             {
  29.                 count[i] = count[i]+1;
  30.                 num = num/i;
  31.             }
  32.     }
  33.     if(num>2)
  34.     {
  35.         p[j++] = num;
  36.         count[num] = count[num] + 1;
  37.     }
  38.  
  39. //    for(i=0;i<j;i++)
  40. //        printf("%d ",p[i]);
  41. //    printf("\n");
  42.     for(i=0;i<j;i++)
  43.     {
  44. //      printf("count of %d is %d\n",p[i],count[p[i]]);
  45.         if(count[p[i]]>max[p[i]])
  46.             max[p[i]] = count[p[i]];
  47. //        printf("maximum power of %d is %d\n",p[i],max[p[i]]);
  48.     }
  49. }
  50. int main()
  51. {
  52.     long long int t;
  53.     long long int a[100001],b[100001],n,x,temp,j,i;
  54.     scanf("%d",&t);
  55.     while(t--)
  56.     {
  57.         long long int lcm=1,cycles=0;
  58.     scanf("%d",&n);
  59.     for(j=1;j<=n;j++)
  60.     {
  61.         scanf("%d",&a[j]);
  62.         b[j] = a[j];
  63.     }
  64.     for(j=1;j<=n;j++)
  65.     {
  66.         if(a[j]!=0)// first
  67.         {
  68.             x = a[j];
  69.             a[j] = 0;
  70.             while(x!=j)
  71.             {
  72.                 temp = x;
  73.                 x = a[x];
  74.                 a[temp] = 0;// to keep track of visited indices they are made 0
  75.             }
  76.         cycles++;
  77.         }
  78.     }
  79.     //printf("%d\n",cycles);
  80.     for(j=1;j<=n;j++)
  81.     {
  82.         int len = 0;
  83.         if(b[j]!=0)
  84.         {
  85.             x = b[j];
  86.             b[j] = 0;
  87.             //printf("%d ",j);
  88.             //len++;
  89.             while(x!=j)
  90.             {
  91.                 //printf("%d ",x);
  92.                 len++;
  93.                 temp = x;
  94.                 x = b[x];
  95.                 b[temp] = 0;
  96.             }
  97.             //printf("%d",x);
  98.             len++;
  99.             //printf("\n");
  100. //            printf("length of each cycle is %d\n",len);
  101.             factors(len);
  102.         }
  103.     }
  104.     for(i=0;i<100000;i++)
  105.     {
  106.         if(i!=0)
  107.         {
  108.             lcm = lcm*pow(i,max[i]);
  109.         }
  110.     }
  111.     printf("%lld\n",lcm);
  112.     }
  113.  
  114. return 0;
  115.  
  116. }
  117.  
Success #stdin #stdout 0.01s 6084KB
comments (?)
stdin
copy 
3
3
1 2 3
5
2 3 1 5 4
14
2 3 4 1 6 7 5 9 10 11 12 8 14 13
stdout
copy 
1
6
60
https://ideone.com/SE3u7N
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!