fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define MAX 70005
  4. #define int long long 
  5.  
  6. int prefix[MAX];
  7. int n,q;
  8.  
  9. void phantich(int x, int j)
  10. {
  11. 	int _x = x;
  12. 	for(int i = 2; i*i <= _x; i++){
  13. 		while(x%i == 0){
  14. 			//cout << i << ' ';
  15. 			prefix[j] ^= i;
  16. 			x /= i;
  17. 		}
  18. 	}
  19. 	if(x > 1) prefix[j] ^= x;
  20. }
  21.  
  22. signed main() {
  23. //	freopen("seqcp.inp","r",stdin);
  24. //	freopen("seqcp.out","w",stdout);
  25. 	cin >> n >> q;
  26. 	prefix[0] = 0;
  27. 	for(int i = 1; i<=n; i++){
  28. 		int a; cin >> a;
  29. 		prefix[i] = prefix[i-1];
  30. 		phantich(a,i);
  31. 	}
  32. 	while(q--){
  33. 		int l,r; cin >> l >> r;
  34. 		if((prefix[r] ^ prefix[l-1]) == 0){
  35. 			cout << "YES" << '\n';
  36. 		}else{
  37. 			cout << "NO" << '\n';
  38. 		}
  39. 	}
  40. 	return 0;
  41. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
3 1
2 3 7
1 3
stdout
copy 
NO
https://ideone.com/uFt5lF
language:
C++14 (gcc 8.3)
created:
10 hours 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!