# Untitled

unknown
plain_text
2 months ago
1.7 kB
0
Indexable
Never
```#pragma GCC optimize("O2,no-stack-protector,unroll-loops")
#define ll long long
#define pb push_back
#define ipar(arr, n) vector<ll> arr(n); for(int i=0;i<n;i++) cin>>arr[i];
#include <cmath>
#include <bits/stdc++.h>
#define pii pair<int, int>;
#define pll pair<ll, ll>;
using namespace std;

void facto(ll n,vector<ll>&primep){
while(n%2==0){
n/=2;
primep[2]++;
}
for(ll i=3;i<=sqrt(n);i+=2){
while(n%i==0){
n/=i;
primep[i]++;
}
}
if(n>2) primep[n]++;
}

void solve(){

/*******************preprocessing******************/
const ll N = 200000;
vector<ll>sqfree(N+1); // sqfree[i] , i is the number not a index
iota(sqfree.begin(),sqfree.end(),0);

for(ll p=2;p<=N;p++){
for(ll c=p;c<=N;c+=p){
ll &cur=sqfree[c];
ll cnt=0;
while(cur%p ==0){
cnt++;
cur/=p;
}
if(cnt%2==1){ // incase the number at sqfree[c] had odd no of prime factors then one prime factor stays in the sqf rep of cur
cur*=p;
}
}
}

ll n;cin>>n;
unordered_map<ll,ll>freq;

ll z=0;
for(ll i=0;i<n;i++){
ll inp; cin>>inp;
if(inp==0) {z++; continue;}

inp=sqfree[inp];
freq[inp]++;
}
ll ans=z*(n-z) + z*(z-1)/2; //1 zero 2 zero
for(auto x:freq){
ll no=x.first;
ll f=x.second;
ans+=f*(f-1)/2;
}
cout<<ans<<"\n";
}

signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1;
//cin>>t;
while(t--) solve();
//cout<<"ok";
}
```