fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main(){
  5.     int n ; cin >> n;
  6.  
  7.     vector<int> nums(n);
  8.     for(int &num : nums) cin >> num;
  9.  
  10.     int maxE = *max_element(nums.begin() , nums.end());
  11.  
  12.     // build SPF array
  13.     vector<int> SPF(maxE + 1);
  14.     iota(SPF.begin() , SPF.end() , 0);
  15.  
  16.     for(int num = 2 ; num * num <= maxE ; num++){
  17.     	if(SPF[num] == num){
  18.     		for(int F = num * num ; F <= maxE ; F += num) if(SPF[F] == F) SPF[F] = num;
  19.     	}
  20.     }
  21.  
  22.     // map every prime number to its positon/index
  23.     int primeId = 0;
  24.     vector<int> primeIndex(maxE + 1);
  25.     for(int num = 2 ; num <= maxE ; num++){
  26.     	if(SPF[num] == num) primeIndex[num] = primeId++;
  27.     }
  28.  
  29.     long long subarrays = 0;
  30.  
  31.     bitset<9600> prod = 0;
  32.     unordered_map<bitset<9600> , int> prefixCnt = { {prod , 1} };
  33.  
  34.     for(int num : nums){
  35.     	int curr = num;
  36.         while(curr != 1){
  37.             int prime = SPF[curr];
  38.             int expo = 0;
  39.             while(curr % prime == 0){
  40.                 curr /= prime;
  41.                 expo += 1;
  42.             }
  43.             if(expo & 1) prod.flip(primeIndex[prime]);
  44.         }
  45.         subarrays += prefixCnt[prod]++;
  46.     }
  47.  
  48.     cout << subarrays;
  49.  
  50.     return 0;
  51. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
10
1 36 111 4 10000 5 625 900 2 2
stdout
copy 
12
https://ideone.com/43YDlk
language:
C++14 (gcc 8.3)
created:
1 day 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!