fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  5. #define endl "\n"
  6. #define ff first
  7. #define ss second
  8. #define mp make_pair
  9. #define pb push_back
  10. #define ll long long
  11. #define int long long
  12.  
  13. #define trace1(x)                cerr<<#x<<": "<<x<<endl
  14. #define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
  15. #define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
  16. #define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
  17. #define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
  18. #define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
  19.  
  20. template<typename T> T gcd(T a,T b) { if(a==0) return b; return gcd(b%a,a); }
  21. template<typename T> T pow(T a,T b, ll m){T ans=1; while(b>0){ if(b%2==1) ans=(ans*a)%m; b/=2; a=(a*a)%m; } return ans%m; }
  22.  
  23. const int N=1e6+5;
  24. const int MOD=1e9+7;
  25.  
  26. int a[N], vis[N], fact[N], sieve[N], primef[N];
  27.  
  28. int modinv(int k)
  29. {
  30. 	return pow(k, MOD-2, MOD);
  31. }
  32.  
  33. void work(int k)
  34. {
  35. 	map<int, int> m;
  36. 	while(k!=1)
  37. 	{
  38. 		m[primef[k]]++;
  39. 		k/=primef[k];
  40. 	}
  41. 	for(auto it:m)
  42. 	{
  43. 		fact[it.ff]=max(fact[it.ff], it.ss);
  44. 	}
  45. }
  46.  
  47. int32_t main()
  48. {
  49. 	IOS;
  50. 	int t;
  51. 	cin>>t;
  52. 	for(int i=2;i<N;i++)
  53. 	{
  54. 		sieve[i]=1;
  55. 	}
  56. 	for(int i=2;i<N;i++)
  57. 	{
  58. 		if(sieve[i])
  59. 		{
  60. 			for(int j=1;i*j<N;j++)
  61. 			{
  62. 				sieve[i*j]=0;
  63. 				primef[i*j]=i;
  64. 			}
  65. 		}
  66. 	}
  67. 	while(t--)
  68. 	{
  69. 		int n;
  70. 		cin>>n;
  71. 		memset(fact, 0, sizeof(fact));
  72. 		for(int i=1;i<=n;i++)
  73. 		{
  74. 			cin>>a[i];
  75. 			vis[i]=0;
  76. 		}
  77. 		vector<int> cycle;
  78. 		for(int i=1;i<=n;i++)
  79. 		{
  80. 			if(vis[a[i]])
  81. 				continue;
  82. 			else
  83. 			{
  84. 				int len=0;
  85. 				int cur=a[i];
  86. 				while(!vis[cur])
  87. 				{
  88. 					vis[cur]=1;
  89. 					len++;
  90. 					cur=a[cur];
  91. 				}
  92. 				cycle.pb(len);
  93. 			}
  94. 		}
  95. 		for(auto it:cycle)
  96. 		{
  97. 			work(it);
  98. 		}
  99. 		int ans=1;
  100. 		for(int i=1;i<N;i++)
  101. 		{
  102. 			if(fact[i]==0)
  103. 				continue;
  104. 			ans*=pow(i, fact[i], MOD);
  105. 			ans%=MOD;
  106. 		}
  107. 		cout<<ans<<endl;
  108. 	}
  109. 	return 0;
  110. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.c:1:25: fatal error: bits/stdc++.h: No such file or directory
 #include <bits/stdc++.h>
                         ^
compilation terminated.
stdout
copy 
Standard output is empty
https://ideone.com/ExHAIG
language:
C (gcc 8.3)
created:
6 years ago
visibility:
secret

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!