fork download 
  1.     #include<iostream>
  2.     #include<cstdio>
  3.     #include<vector>
  4.     #include<algorithm>
  5.     #define NMOD 1000000007
  6.     using namespace std;
  7.     vector<int> vj(100001);
  8.     vector<bool> vi(100001,false);
  9.     long  gcd(long u,long v)
  10.     {
  11.     if (u == v)
  12.     return u;
  13.     if (u == 0)
  14.     return v;
  15.     if (v == 0)
  16.     return u;
  17.     if (~u & 1)
  18.     {
  19.     if (v & 1)
  20.     return gcd(u >> 1, v);
  21.     else
  22.     return gcd(u >> 1, v >> 1) << 1;
  23.     }
  24.     if (~v & 1)
  25.     return gcd(u, v >> 1);
  26.     if (u > v)
  27.     return gcd((u - v) >> 1, v);
  28.     return gcd((v - u) >> 1, u);
  29.     }
  30. //    long lcm(long a,long b)
  31. //    {
  32. //      long g=gcd(a,b);
  33. //    a=(a*b);
  34. //    a=a/g;
  35. //    return a;
  36. //    }
  37. //    long  dp(int a,int b,long int c)
  38. //    {
  39. //    vi[a]=true;
  40. //    if(a==b)
  41. //    return c;
  42. //    else
  43. //    return dp(vj[a]-1,b,c+1);
  44. //    }
  45.     main()
  46.     {	
  47.     int ti,t,n,i;
  48.     scanf("%d",&t);
  49.     for(ti=0;ti<t;ti++)
  50.     {
  51.     scanf("%d",&n);
  52.     for(i=0;i<n;i++)
  53.     scanf("%d",&vj[i]);
  54.     bool depth[200002]={false};
  55.     long long pro1[100001];
  56. 	long gd[100001];
  57.     long long c=0,a,j=1;
  58.     for(i=0;i<n;i++)
  59.     {
  60.     if(vi[i]==false)
  61.     {
  62.     	vi[i]=true;
  63.     	a=vj[i]-1;
  64.     	j=1;
  65.     	while(true)
  66.     	{
  67.     		vi[a]=true;
  68.     		if(a==i)
  69.     		{
  70.     	        if(depth[j]==false)
  71.     			pro1[c++]=j;
  72.     			depth[j]=true;
  73.     			break;
  74. 			}
  75. 			else
  76. 			{
  77. 				a=vj[a]-1;
  78. 				j++;
  79. 			}
  80.     	}
  81.     }
  82. 	}
  83.    // pro1[c++]=dp(vj[i]-1,i,1);
  84.  
  85.    for(i=0;i<c;i++)
  86.      printf("\n\t\t%d",pro1[i]);
  87.    gd[0]=pro1[0];
  88.     if(c>=2)
  89.     {
  90.     for(i=1;i<c;i++)
  91.     gd[i]=gcd(pro1[i],gd[i-1]);	
  92.     for(i=1;i<c;i++)
  93.     pro1[i]=((pro1[i]%NMOD)*(pro1[i-1]%NMOD))%NMOD;
  94. 	}
  95. 	for(i=1;i<c;i++)
  96.     pro1[c-1]=(pro1[c-1]/gd[c-1]);
  97.     printf("%lld %ld\n",pro1[c-1],gd[c-1]);
  98.     for(i=0;i<n+1;i++)
  99.     vi[i]=false;
  100.     }
  101.     }
  102.  
  103.  
Success #stdin #stdout 0s 4724KB
comments (?)
stdin 
5
5
2 3 1 5 4
stdout 
		3
		26 1

		3
		26 1

		3
		26 1

		3
		26 1

		3
		26 1
https://ideone.com/GxMgch
language:
C++ (gcc 8.3)
created:
11 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!