fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 2e5 + 2;
  5.  
  6. unordered_set<int> primes;
  7. vector<int> ordered_primes;
  8.  
  9. unordered_map<int, int> bit[N]; 
  10.  
  11. void sieve(int n) {
  12. 	vector<bool> isPrime(n + 1, true);
  13. 	for (int i = 2; i * i <= n; i++) {
  14. 		if (isPrime[i]) {
  15. 			for (int j = i * i; j <= n; j += i) {
  16. 				isPrime[j] = false;
  17. 			}
  18. 		}
  19. 	}
  20. 	for (int i = 2; i <= n; i++) {
  21. 		if (isPrime[i]) {
  22. 			primes.insert(i);
  23. 			ordered_primes.push_back(i);
  24. 		}
  25. 	}
  26. }
  27.  
  28. int query(int i, int val) {
  29. 	int ret = 0;
  30. 	for (int j = i; j >= 1; j -= j & -j) {
  31. 		if (bit[j].find(val) != bit[j].end()) {
  32. 			ret += bit[j][val];	
  33. 		}
  34. 	}
  35. 	return ret;
  36. }
  37.  
  38. // how many to the left of i is equal to val * another prime
  39. int query2(int i, int val) {
  40. 	int ret = 0;
  41. 	for (int j = i; j >= 1; j -= j & -j) {
  42. 		for (auto it = bit[j].begin(); it != bit[j].end(); it++) {
  43. 			int key = (*it).first;
  44. 			if (key % val == 0 && primes.find(key / val) != primes.end()) {
  45. 				ret += bit[j][key];
  46. 			}
  47. 		}
  48. 	}
  49. 	return ret;
  50. }
  51.  
  52. void solve() {
  53. 	// cout << "---"<<endl;
  54. 	int n;
  55. 	cin >> n;
  56. 	vector<int> a(n + 1);
  57.  
  58. 	for (int i = 1; i <= n; i++) {
  59. 		bit[i].clear();
  60. 	}
  61.  
  62. 	for (int i = 1; i <= n; i++) {
  63. 		cin >> a[i];
  64.  
  65. 		for (int j = i; j <= n; j += j & -j) {
  66. 			bit[j][a[i]]++;
  67. 		}
  68. 	}
  69.  
  70. 	vector<int> suffix(n + 2, 0);
  71.  
  72. 	for (int i = n; i >= 1; i--) {
  73. 		suffix[i] = suffix[i + 1];
  74. 		if (primes.find(a[i]) != primes.end()) {
  75. 			suffix[i] += 1;
  76. 		}
  77. 	}
  78.  
  79. 	int ans = 0;
  80. 	for (int i = 1; i <= n; i++) {
  81. 		// if a[i] is not a prime
  82. 		if (primes.find(a[i]) == primes.end()) {
  83. 			// check if a[i] is a product of two primes
  84. 			int p1 = 0, p2 = 0;
  85. 			for (int j = 0; j < ordered_primes.size(); j++) {
  86. 				if (ordered_primes[j] * ordered_primes[j] > a[i]) break;
  87. 				if (a[i] % ordered_primes[j] == 0 && 
  88. 					primes.find(a[i] / ordered_primes[j]) != primes.end()) {
  89. 						// cout << "[i: " << i << "] is a product of 2 primes" << endl;
  90. 						ans++;
  91. 						p1 = ordered_primes[j];
  92. 						p2 = a[i] / ordered_primes[j];
  93. 						break;
  94. 					}
  95. 			}
  96. 			if (p1) {
  97. 				ans += query(n, p1) - query(i, p1);
  98. 				if (p1 != p2) ans += query(n, p2) - query(i, p2);
  99.  
  100. 				ans += query(n, a[i]) - query(i, a[i]);
  101. 			}
  102. 			continue;
  103. 		}
  104.  
  105. 		// primes to the right of i
  106. 		int suff = suffix[i + 1]; 
  107. 		ans += suff;
  108.  
  109. 		// minus the duplicates primes to the right of i
  110. 		int b = query(n, a[i]) - query(i, a[i]);  
  111. 		ans -= b;
  112.  
  113. 		// add composite numbers to the right of i where a[j] = a[i] * another prime
  114. 		int c = query2(n, a[i]) - query2(i, a[i]); 
  115. 		ans += c;
  116.  
  117. 		// cout << "[i: " << i << "] " << "suff: " << suff << ", b: " << b << ", c: " << c << endl;
  118. 	}
  119.  
  120. 	cout << ans << endl;
  121. }
  122.  
  123. int main() {
  124. 	sieve(N);
  125. 	int t;
  126. 	cin >> t;
  127. 	while (t--) solve();
  128. }
  129.  
  130.  
Success #stdin #stdout 0.02s 15168KB
comments (?)
stdin
copy 
1
23
4 17 12 18 13 2 18 8 17 21 15 19 14 5 6 21 8 6 22 4 17 22 17
stdout
copy 
44
https://ideone.com/1UG6v2
language:
C++14 (gcc 8.3)
created:
12 days 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!