fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define int long long
  5. #define ll long long
  6. #define MAX 70005
  7.  
  8. ll ramdomly()
  9. {
  10.     ll tmp = rand();
  11.     tmp %= 17;
  12.     ll ans = 1;
  13.     for(int i = 1; i<= 17; i++) ans*= 10;
  14.     return ans + rand();
  15. }
  16.  
  17. int prefix[MAX];
  18. int n,q;
  19. map<int,int> mp;
  20.  
  21. void phantich(int x, int j)
  22. {
  23. 	int _x = x;
  24. 	for(int i = 2; i*i <= _x; i++){
  25. 		while(x%i == 0){
  26. 			//cout << i << ' ';
  27. 			//prefix[j] ^= i;
  28. 			if(!mp.count(i)){
  29.                 mp[i] = ramdomly();
  30. 			}
  31. 			prefix[j] ^= mp[i];
  32. 			x /= i;
  33. 		}
  34. 	}
  35. 	if(x > 1){
  36.         if(!mp.count(x)) mp[x] = ramdomly();
  37.         prefix[j] ^= mp[x];
  38. 	}
  39. }
  40.  
  41. signed main() {
  42. 	freopen("seqcp.inp","r",stdin);
  43. 	freopen("seqcp.out","w",stdout);
  44.  
  45. 	cin >> n >> q;
  46. 	prefix[0] = 0;
  47. 	for(int i = 1; i<=n; i++){
  48. 		int a; cin >> a;
  49. 		prefix[i] = prefix[i-1];
  50. 		phantich(a,i);
  51. 	}
  52. 	while(q--){
  53. 		int l,r; cin >> l >> r;
  54. 		if((prefix[r] ^ prefix[l-1]) == 0){
  55. 			cout << "YES" << '\n';
  56. 		}else{
  57. 			cout << "NO" << '\n';
  58. 		}
  59. 	}
  60. 	return 0;
  61. }
  62.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/BIYvQg
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!