fork download
copy 
  1. //#pragma GCC optimize("Ofast")
  2. //#pragma GCC target("avx,avx2,fma")
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. #define ll long long
  6. #define fi first
  7. #define se second
  8. #define MOD 1000000007
  9. #define FOR(i,a,b) for (int i = (a);i <= (b);i++)
  10. #define FOD(i,a,b) for (int i = (b);i >= (a);i--)
  11. #define ALL(x) (x).begin(),(x).end()
  12. #define ii pair<ll,ll>
  13. #define iii pair<ll,pair<ll,int>>
  14. //const int MOD = 998244353;
  15. const int MAXN = 1e6 + 7;
  16. int a[MAXN],prime[MAXN],dd[MAXN];
  17. void sieve(){
  18.     FOR(i,2,MAXN)if (!prime[i]){
  19.         prime[i] = i;
  20.         for (ll j = 1ll * i * i;j <= MAXN;j+=i)prime[j] = i;
  21.     }
  22. }
  23. int main(){
  24.     ios_base::sync_with_stdio(false);
  25.     cin.tie(0); cout.tie(0);
  26.     //freopen("COMNUM.inp","r",stdin);
  27.     //freopen("COMNUM.out","w",stdout);
  28.     sieve();
  29.     int n;cin >> n;
  30.     FOR(i,1,n)cin >> a[i];
  31.     ll ans = 0;
  32.     FOR(i,1,n){
  33.         int p = 1;
  34.         while (a[i] > 1){
  35.             int d = prime[a[i]];
  36.             int cnt = 0;
  37.             while(a[i] % d == 0){
  38.                 a[i] = a[i] / d;
  39.                 cnt++;
  40.             }
  41.             if (cnt & 1)p = p * d;
  42.         }
  43.         ans = ans + dd[p];
  44.         dd[p]++;
  45.     }
  46.     cout << ans;
  47.     return 0^0;
  48. }
Success #stdin #stdout 0.01s 8204KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
14750596
https://ideone.com/o4fbVr
language:
C++ (gcc 8.3)
created:
4 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!