fork download
copy 
  1. #include <bits/stdc++.h> 
  2. using namespace std;  
  3.  
  4. typedef long long ll;  
  5. typedef pair<int, int> ii;  
  6.  
  7. const int INF = 1e9;  
  8. const ll LINF = 1e18;  
  9.  
  10. const int N = 2e5 + 5; 
  11. const int Q = 2e5 + 5; 
  12. const int MAX_A = 1e6; 
  13. const int B = 400; 
  14.  
  15. struct Query {
  16. 	int l, r, idx; 
  17. 	bool operator<(const Query& other) const {
  18. 		if (l / B == other.l / B) {
  19. 			return (l / B & 1) ? (r > other.r) : (r < other.r); 
  20. 		}
  21. 		return l < other.l; 
  22. 	}
  23. }; 
  24.  
  25. int n, q; 
  26. vector<ii> a[N];
  27. vector<Query> queries; 
  28.  
  29. vector<ii> factorize(int x) {
  30. 	vector<ii> ans; 
  31. 	for (int i = 2; i * i <= x; i++) {
  32. 		if (x % i == 0) {
  33. 			int e = 0;   
  34. 			while (x % i == 0) {
  35. 				x /= i;  
  36. 				e++; 
  37. 			}
  38. 			ans.push_back({i, e}); 
  39. 		}
  40. 	}
  41. 	if (x > 1) ans.push_back({x, 1}); 
  42. 	return ans; 
  43. }
  44.  
  45. int cur_ans; 
  46. int cnt[MAX_A + 5]; // cnt[p] = số mũ mod cho 3 của thừa số nguyên tố p 
  47. int cnt_mod[3]; // cnt_mod[r] = số lượng p sao cho cnt[p] = r (mod 3)
  48. int ans[Q]; 
  49.  
  50. void add(int i) {
  51. 	for (ii p : a[i]) {
  52. 		cnt_mod[cnt[p.first]]--; 
  53. 		cnt[p.first] = (cnt[p.first] + p.second) % 3;
  54. 		cnt_mod[cnt[p.first]]++; 
  55. 	}
  56. 	cur_ans = (cnt_mod[1] == 0 && cnt_mod[2] == 0); 
  57. }
  58.  
  59. void remove(int i) {
  60. 	for (ii p : a[i]) {
  61. 		cnt_mod[cnt[p.first]]--; 
  62. 		cnt[p.first] = ((cnt[p.first] - p.second) % 3 + 3) % 3;  
  63. 		cnt_mod[cnt[p.first]]++; 
  64. 	}
  65. 	cur_ans = (cnt_mod[1] == 0 && cnt_mod[2] == 0); 
  66. }
  67.  
  68. int main() {
  69. 	ios::sync_with_stdio(0); cin.tie(0);  	
  70. 	cin >> n >> q; 
  71. 	for (int i = 1; i <= n; i++) {
  72. 		int x; cin >> x; 
  73. 		a[i] = factorize(x);  
  74. 	}
  75.  
  76. 	for (int i = 0; i < q; i++) {
  77. 		int l, r; 
  78. 		cin >> l >> r; 
  79. 		queries.push_back({l, r, i}); 
  80. 	}
  81.  
  82. 	sort(queries.begin(), queries.end());  
  83.  
  84. 	cur_ans = 0; 
  85. 	int cur_l = 1, cur_r = 0; 
  86.  
  87. 	for (Query q : queries) {
  88. 		while (cur_l > q.l) {
  89. 			cur_l--; 
  90. 			add(cur_l); 
  91. 		}
  92.  
  93. 		while (cur_r < q.r) {
  94. 			cur_r++; 
  95. 			add(cur_r); 
  96. 		}
  97.  
  98. 		while (cur_l < q.l) {
  99. 			remove(cur_l); 
  100. 			cur_l++; 
  101. 		}
  102.  
  103. 		while (cur_r > q.r) {
  104. 			remove(cur_r); 
  105. 			cur_r--; 
  106. 		}
  107.  
  108. 		ans[q.idx] = cur_ans; 
  109. 	}
  110.  
  111. 	for (int i = 0; i < q; i++) {
  112. 		cout << (ans[i] ? "Yes" : "No") << '\n'; 
  113. 	}
  114. }
Success #stdin #stdout 0.01s 8720KB
comments (?)
stdin
copy 
8 5
7 49 30 1 15 8 6 10
1 2
2 3
4 4
5 8
3 8
stdout
copy 
Yes
No
Yes
No
Yes
https://ideone.com/IZlseA
language:
C++14 (gcc 8.3)
created:
1 year 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!