fork(1) download
copy 
  1. #include <stdio.h>
  2. #include <math.h>
  3. #include <iostream>
  4. #include <string.h>
  5. #include <vector>
  6. #define LL long long
  7. #define MOD 1000000007
  8. #define MAX(a,b) ((a>b)?a:b)
  9. using namespace std;
  10. /*
  11. 	Fast input via getchar_unlocked
  12. */
  13. inline void fastInt(int &a){
  14. 	char c;
  15. 	while(c<33 || c=='-'){
  16. 		 c=getchar_unlocked();
  17. 	}
  18. 	a=0;
  19. 	while(c>33){
  20. 		a=(a*10)+c-'0';
  21. 		c=getchar_unlocked();
  22. 	}
  23. }
  24. int visited[1000010]; //Prunning
  25. int p[1000010]; //Pi's 
  26. int r[1000010]; //Lenghts of the cycles
  27. int primes[80000]; //Primes below 10^6
  28. int ind[1000010]; //Index of a prime number i in the array "primes"
  29. bool sieve[1000010]; //Prime or Not? Array
  30. int tamp; //Amount of primes 
  31. /* Sieve of Eratosthenes to obtain primes below 10^6 */
  32. void fill_sieve(){
  33. 	memset(sieve, true, sizeof(sieve));
  34. 	for(int i=2; i<(int)sqrt(1000000); i++){
  35. 		if(!sieve[i]) continue;
  36. 		for(int j=i; j*i<=1000000; j++){
  37. 			sieve[i*j] = false;
  38. 		}
  39. 	}
  40. 	tamp = 0;
  41. 	sieve[0] = sieve[1] = false;
  42. 	for(int i=0; i<=1000000; i++) {
  43. 		if(sieve[i]){ 
  44. 			primes[tamp++] = i; //Storing the primes and their respective indexes
  45. 			ind[i] = tamp-1;
  46. 		} 
  47. 	}
  48. }
  49. int pot[80000]; //Power of a prime factor
  50. /*
  51. 	There are less than 80000 primes below 10^6, so
  52. 	I used an array of that size to store them!
  53. */
  54. /* Trial division to obtain the prime factorization of "num"*/
  55. int K;
  56. void f(int num){
  57. 	if(sieve[num]){
  58. 		pot[ind[num]] = MAX(pot[ind[num]], 1);
  59. 		return;
  60. 	}
  61. 	int cont;
  62. 	cont = 0;
  63. 	int idx=0;
  64.  
  65. 	while(primes[idx]*primes[idx]<=num){
  66. 		if (num%primes[idx]==0){
  67. 			num/=primes[idx];
  68. 			visited[num] = K+1;            //Don't factorize the same number again
  69. 			cont++;
  70. 			pot[idx] = MAX(pot[idx], cont);
  71. 		}else{
  72. 			cont = 0;
  73. 			idx++;
  74. 		}
  75. 	}
  76. 	if (num>1){ 
  77. 		if(primes[idx]==num) pot[ind[num]] = MAX(pot[ind[num]], cont+1);
  78. 		else pot[ind[num]] = MAX(pot[ind[num]], 1);
  79. 	}	
  80. }
  81. /*
  82. 	Fast Exponentiation
  83. */
  84. LL fpow (LL a, LL b){
  85.  
  86. 	LL ans=1LL;
  87. 	while (b){
  88. 		if (b&1) ans= (ans*a)%MOD;
  89. 		a= (a * a) %MOD;
  90. 		b>>=1;
  91. 	}
  92.  
  93. 	return ans;
  94. }
  95. int done[1000010]; //Length already stored?
  96. int main(){
  97. 	fill_sieve();
  98. 	int n;
  99. 	int T= 0;
  100. 	K = 0;
  101. 	while(scanf("%d", &n)!=-1){
  102. 		for(int i=1; i<=n; i++) fastInt(p[i]);
  103. 		int tam = 0;
  104. 		/*
  105. 			Disjoint cycle finding
  106. 			Iterate over all Pi, if a position is not visited,
  107. 			start counting the cycle until we reach a already
  108. 			visited position
  109. 		*/
  110. 		for(int i=1; i<=n; i++){
  111. 			if(visited[i]!=K+1){
  112. 				r[tam] = 0;
  113. 				int P = i;
  114. 				while(visited[P]!=K+1){
  115. 					visited[P] = K+1;
  116. 					r[tam]++;
  117. 					P = p[P];
  118. 				}
  119. 				if(done[r[tam]]!=T+1){    //Don't store a number previously stored
  120. 					done[r[tam]] = T+1;
  121. 					tam++;
  122. 				}
  123. 			}
  124. 		}
  125. 		K++;
  126. 		memset(pot, 0, sizeof(pot)); //Set to 0 all the power of the prime numbers
  127. 		for(int i=0; i<tam; i++){
  128. 			if(visited[r[i]]==K+1) continue; //If the length is already factorized, don't do it again
  129. 			visited[r[i]] = K+1;
  130. 			f(r[i]);
  131. 		}
  132. 		K+=2;
  133. 		LL x = 1LL;
  134. 		for(int i=0; i<tamp; i++){
  135. 			LL X = fpow(primes[i], pot[i]); //Obtaining the LCM via prime powers multiplication
  136. 			x = (x*X)%MOD; //Modular multiplication (a*b)%p = ((a%p)*(b%p))%p to avoid overflow
  137. 		}
  138. 		T++;
  139. 		printf("%lld\n", x);
  140. 	}
  141. 	return 0;
  142. }
  143.  
Success #stdin #stdout 0.01s 24232KB
comments (?)
stdin
copy 
4
2 1 3 4
stdout
copy 
2
https://ideone.com/q6xSKd
language:
C++ (gcc 8.3)
created:
9 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!