fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define el '\n'
  4. #define oo LLONG_MAX >> 2
  5. #define all(x) x.begin(), x.end()
  6. #define allr(x) x.rbegin(), x.rend()
  7. #define pb push_back
  8. #define pep_Guardiola                                                          \
  9.   ios::sync_with_stdio(0);                                                     \
  10.   cin.tie(0);                                                                  \
  11.   cout.tie(0);
  12. using namespace std;
  13. const int N = 1e6 + 7;
  14. int spf[N];
  15. signed main() {
  16.   pep_Guardiola;
  17.   for (int i = 2; i < N; i++) {
  18.     if (!spf[i]) {
  19.       spf[i] = i;
  20.       for (int j = i * i; j < N; j += i)
  21.         if (!spf[j])
  22.           spf[j] = i;
  23.     }
  24.   }
  25.   int n;
  26.   cin >> n;
  27.   map<int, int> mp;
  28.   int ans = 0;
  29.   for (int i = 0; i < n; i++) {
  30.     int x;
  31.     cin >> x;
  32.     int cur = 1;
  33.     while (spf[x]) {
  34.       int p = spf[x];
  35.       bool odd = 0;
  36.       while (x % p == 0)
  37.         x /= p, odd ^= 1;
  38.       cur *= (odd ? p : 1);
  39.     }
  40.     cur *= x;
  41.     ans += mp[cur]++;
  42.   }
  43.   cout << ans << el;
  44. }
  45.  
Success #stdin #stdout 0.02s 11416KB
comments (?)
stdin
copy 
5
8 5 8 10 8
stdout
copy 
3
https://ideone.com/R2DhkW
language:
C++ (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!