fork(3) download
copy 
  1. // sandeep_007	
  2.  
  3. #include <bits/stdc++.h>
  4.  
  5. using namespace std;
  6.  
  7. #define PI acos(-1)
  8. #define mod 1000000007
  9. #define ll long long
  10. #define nitro std::ios_base::sync_with_stdio (false); cin.tie(NULL)
  11. #define pb push_back
  12. #define mp make_pair
  13. #define vi vector < int >
  14.  
  15. bool sortbysec(const pair<int,int> &a,
  16.               const pair<int,int> &b){
  17.     return (a.second < b.second);
  18. }
  19.  
  20. inline ll mx(ll a,ll b){
  21. 	if(a > b) return a;
  22. 	else return b;	
  23. }
  24.  
  25. ll gcd(ll a,ll b){if(b==0) return a; else return gcd(b,a%b);}
  26.  
  27. ll power(ll x,ll y,ll p){
  28.     ll res = 1;   
  29.     x = x % p;    
  30.     while (y > 0){
  31.         if (y & 1)
  32.             res = (res*x) % p;
  33.  
  34.         y = y>>1; 
  35.         x = (x*x) % p; 
  36.     }
  37.     return res;
  38. }
  39.  
  40. int main(){
  41. 	nitro;
  42. 	//prime(10000000);
  43.  
  44. 	#ifdef DBG
  45. 		freopen("in","r",stdin);
  46. 	#endif
  47.  
  48. 	ll n;
  49. 	cin >> n;
  50. 	map<ll,ll> mymap;
  51.  
  52. 	for(ll k=0;k<n;k++){
  53. 		ll m;	
  54. 		cin >> m;
  55. 		ll c = 0;
  56. 		map<ll,ll> mymap2;
  57. 		for(ll j=0;j<m;j++){
  58. 			ll a;			
  59. 			cin >> a;
  60. 			if(k == 0){	
  61. 				c=0;			
  62. 				while(a%2 == 0){
  63. 					a=a/2;
  64. 					c++;
  65. 				}
  66. 				if(mymap.find(2) == mymap.end())
  67. 					mymap[2] = c;
  68. 				else
  69. 					mymap[2] += c;
  70.  
  71. 				for(ll i=3;i<=sqrt(a);i+=2){
  72. 					if(a%i == 0){
  73. 						c = 0;
  74. 						while(a%i == 0){
  75. 							a = a/i;
  76. 							c+=1;
  77. 						}
  78. 						if(mymap.find(i) == mymap.end())
  79. 							mymap[i] = c;
  80. 						else
  81. 							mymap[i] += c;
  82. 					}	
  83. 				}
  84. 				if(a > 2)
  85. 					if(mymap.find(a) == mymap.end())
  86. 						mymap[a] = 1;
  87. 					else
  88. 						mymap[a] += 1;	
  89. 			}
  90. 			else{
  91. 				if(a%2 == 0){
  92. 					c=0;
  93. 					while(a%2 == 0){
  94. 						a=a/2;
  95. 						c+=1;	
  96. 					}
  97. 					if(mymap2.find(2) == mymap2.end())
  98. 						mymap2[2] = c;
  99. 					else
  100. 						mymap[2] += c;
  101. 				}		
  102. 				for(int j=3;j<=sqrt(a);j+=2){
  103. 					if(a%j == 0){
  104. 						c=0;					
  105. 						while(a%j == 0){
  106. 							a=a/j;
  107. 							c+=1;
  108. 						}
  109. 						if(mymap2.find(j) == mymap2.end())
  110. 							mymap2[j] = c;
  111. 						else
  112. 							mymap2[j] += c;
  113. 					}	
  114. 				}
  115. 				if(a > 2){
  116. 					if(mymap2.find(a) == mymap2.end())
  117. 						mymap2[a] = 1;
  118. 					else
  119. 						mymap2[a] += 1;				
  120. 				}
  121. 			}
  122. 		}
  123. 		if(k > 0){
  124. 			map < ll,ll>::iterator it;
  125. 			it = mymap.begin();	
  126. 			while(it != mymap.end()){
  127. 				if(mymap2.find(it->first) == mymap2.end())
  128. 					mymap[it->first] = 0;
  129. 				else	
  130. 					mymap[it->first] = min(mymap[it->first],mymap2[it->first]);	
  131. 				it++;	
  132. 			}		
  133. 		} 	
  134. 	}
  135.  
  136. 	map < ll ,ll>::iterator it;
  137. 	it = mymap.begin();
  138. 	ll ans = 1;	
  139.  
  140. 	while(it != mymap.end()){
  141. 		ans = (ans*power(it->first,it->second,mod))%mod;
  142. 		it++;		
  143. 	}
  144.  
  145. 	cout << ans << "\n";
  146.  
  147. 	return 0;	
  148. }
Success #stdin #stdout 0s 16056KB
comments (?)
stdin
copy 
2
11 1 2 3 4 5 6 7 8 9 10 11
2 1024 15
stdout
copy 
3840
https://ideone.com/2afY09
language:
C++14 (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!