fork download 
  1. #include <bits/stdc++.h>
  2. typedef long long ll;
  3. using namespace std;
  4.  
  5. ll n, a[300010], nt[1000100];
  6. map<ll, ll>mp;
  7.  
  8. void sang()
  9. {
  10.     nt[1] = 1;
  11.     for (int i=2; i<=1000; i++) if (!nt[i])
  12.     {
  13.         for (int j=i*i; j<=1000000; j+=i) nt[j] = i;
  14.     }
  15.     for (int i=1; i<=1000000; i++) if (!nt[i]) nt[i] = i;
  16. }
  17.  
  18. int main()
  19. {
  20.     cin >> n;
  21.     sang();
  22.     for (int i=1; i<=n; i++) cin >> a[i];
  23.     for (int i=1; i<=n; i++)
  24.     {
  25.         vector<ll>vec;
  26.         ll tmp = a[i];
  27.         while (a[i] > 1)
  28.         {
  29.             if (vec.empty() || nt[a[i]] != vec.back()) vec.push_back(nt[a[i]]);
  30.             a[i] /= nt[a[i]];
  31.         }
  32.         // if (vec.empty() || nt[a[i]] != vec.back()) vec.push_back(nt[a[i]]);
  33.         for (ll v : vec) while (tmp % (v*v) == 0) tmp /= v*v;
  34.         a[i] = tmp;
  35.     }
  36.     for (int i=1; i<=n; i++) mp[a[i]]++;
  37.     ll ret = 0;
  38.     for (int i=1; i<=n; i++) if (mp[a[i]])
  39.     {
  40.         ret += mp[a[i]]*(mp[a[i]]-1) / 2;
  41.         mp[a[i]] = 0;
  42.     }
  43.     cout << ret;
  44. }
Success #stdin #stdout 0.02s 11408KB
comments (?)
stdin 
4
1 2 4 8
stdout 
2
https://ideone.com/9hI9T1
language:
C++14 (gcc 8.3)
created:
13 days 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!