fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll  long long
  3. #define pb push_back
  4. #define mp make_pair
  5. #define ff first
  6. #define ss second
  7. #define br cout <<"\n";
  8. #define all(x)  (x).begin(),(x).end()
  9. #define rall(x)  (x).rbegin(),(x).rend()
  10. #define tr(c,i) for(auto i : c)
  11. #define pii pair< int,int >
  12. #define fast_io() ios_base::sync_with_stdio(false);cin.tie(nullptr)
  13. #define pq priority_queue< pair<ll,pii> ,vector<pair<ll,pii>>,greater <pair<ll,pii>> >p;//container adapter makes ascending q
  14. using namespace std;
  15. const int dx[] = { 1, -1 , 0 , 0  };
  16. const int dy [] = { 0 ,0 , 1 , -1  };
  17. const int MOD = 1000 * 1000 * 1000 + 7 ;
  18. const int N = 4  ;
  19. const int MAXN = 1000*100 + 5 ;
  20. const int INF = INT_MAX ;
  21. ll res = 0 ; 
  22. vector<int>spf(MAXN) ;
  23. map<int , int >xmap ,ymap;
  24. void precompute(){
  25. 	iota( all(spf) ,  0) ;  
  26. 	for (int i = 2 ; i < MAXN ; i+=2 )
  27. 		spf[i] = 2 ;
  28. 	for (int i = 3 ; i < MAXN ; i+=2 )
  29. 	{	if (spf[i] == i ){
  30. 		for (int j =  1 ; i*j < MAXN ; ++j )
  31. 			spf[i*j] = min( spf[i * j ], i ) ;
  32. 		}
  33. 	}	
  34. }
  35. vector<pair<int , int >> getPrime(ll x ){
  36. 	map<int , int >prime  ; 
  37. 	while (x != 1 )
  38. 	{	prime[spf[x]]++ ; 
  39. 		x = x / spf[x] ;
  40.  
  41. 	}
  42. return vector<pair<int,int >>(all(prime)) ; 
  43.  
  44. 	} 
  45. void getValidPair(int k,  ll cur , int idx , vector<pair<int,int >> &prime , map<int , int >&mp )
  46. {	if (idx == (int)prime.size()  )
  47. 	{
  48. 		// cout << cur << " " ; 
  49. 		auto curp = mp.find(cur );
  50. 		auto curd = mp.find((1ll*k * k )/cur );
  51.  
  52. 		if (curp != mp.end() and curd != mp.end())
  53. 			{
  54. 				// cout << cur <<"---->";br
  55. 				res ++ ;
  56. 			}
  57.  
  58. 		// cur = -cur ;	
  59. 		// auto curn = mp.find( cur );
  60. 		// curd = mp.find((-1ll* k * k )/cur );
  61.  
  62. 		// if (curn != mp.end() and curd != mp.end())
  63. 			// {
  64. 				// cout << cur <<"=====" << curd->ff ;br
  65. 				// res++ ;
  66. 				// } 
  67. 		return ; 
  68. 	}
  69. 	ll num = prime[idx].ff , p = prime[idx].ss ; 			
  70. 	for (int i = 0 ; i <= (p << 1 ) ; ++ i ) 
  71. 	{
  72. 		getValidPair(k , cur , idx+1 , prime ,mp );
  73. 		cur *= num ; 	
  74. 	}	
  75. } 
  76. void display(vector<pair<int , int >>&prime){
  77. for (auto x : prime )
  78. cout << x.ff <<" "<<x.ss <<"\n";
  79. 	}
  80. int main (){
  81.  
  82. precompute();
  83.  
  84.  
  85.  
  86. int t = 1 ;
  87. // cin >> t ;
  88. while (t--){
  89. int n , m ;
  90. cin >> n >> m ;
  91. cout <<  n << " " << m ; br
  92. vector<int>x, y;
  93. bool zero = false ;
  94. for (int i = 0 ; i < n ; ++ i  ){
  95. 	int inp ; 
  96. 	cin >> inp ;
  97.  
  98. 	if (inp)		
  99. 	{
  100. 		x.pb(inp) ;
  101. 		xmap[inp] ++ ;  
  102. 	} 
  103. 	else
  104. 	{
  105. 		zero = true ; 
  106. 		--n ;
  107. 	}
  108.  
  109. 	}
  110.  
  111. for (int i = 0 ; i < m ; ++ i  ){
  112. 	int inp ;  
  113. 	cin >> inp ;
  114. 	cout << inp ;
  115. 	br 
  116. 	if(inp != 0 )
  117. 	{
  118. 		y.pb(inp) ; 
  119. 		ymap[inp]++ ; 
  120. 	}
  121. 	else
  122. 	{
  123. 		zero = true ;
  124. 		br 
  125. 		--m;
  126.  
  127. 	}
  128. 	cout << i ;
  129. 	}
  130. 	if(zero) 
  131. 	res = n * m ;
  132. 	cout << n << " "<< m ;
  133. 	br
  134.  
  135.  
  136. 	//y^2 = - (x1 * x2) ;     
  137. 		for (auto j : y ){
  138. 			vector<pair<int , int >>prime = getPrime(abs(j)); 
  139. 			//cout << j << "-------\n" ; display(prime) ;
  140. 			//cout << "\nAll Divisors "<< j <<endl  ; 
  141. 			getValidPair(j,1,0,prime,xmap); 
  142. 	}
  143.  
  144. 	//x^2 = - (y1 * y2 )
  145. 		for (auto i : x ){
  146. 			vector<pair<int , int >>prime = getPrime(abs(i));
  147. 			//cout << i << "-------\n" ; display(prime) ;
  148. 			//cout << "\nAll Divisors "<< i <<endl  ; 
  149. 			getValidPair(i,1,0,prime,ymap); 
  150. 	}
  151.  
  152.  
  153.  
  154. cout << res ;
  155. br	
  156. }
  157.  
  158.  
  159.  
  160.  
  161.  
  162. return 0 ;
  163.  
  164. }
  165.  
  166. // 2 year => 2 3 -> 6 5 1 5 5 1 5 
  167.  
Success #stdin #stdout 0s 4528KB
comments (?)
stdin
copy 
4 7
6 2 1 4 
0 0 0 0 0 0 0
stdout
copy 
4 7
0

00

10

20

34 3
12
https://ideone.com/N7yccw
language:
C++14 (gcc 8.3)
created:
4 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!