abc342D 乘积为完全平方数的对数

题面：给定长为n的数组A，问有多少对下标(i,j)满足A[i]*A[j]为完全平方数？
范围：n<=2E5; A[i]<=2E5

思路：完全平方数即质因子的个数为偶数，因此对元素进行化简，把偶次质因子都去掉，再统计即可。另外，0乘任何数都为0，需要单独处理。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,b) for(int i=a; i<=b; i++)
#define per(i,a,b) for(int i=b; i>=a; i--)

map<int,int> factor(int z) {
    map<int,int> p;
    for (int i = 2; i <= z/i; i++) {
        while (z % i == 0) {
            p[i] += 1;
            z /= i;
        }
    }
    if (z > 1) p[z] += 1;
    return p;
}

void solve() {
    int n;
    cin >> n;
    int ans = 0, cnt0 = 0;
    map<int,int> cnt;
    rep(i,1,n) {
        int A;
        cin >> A;
        if (A == 0) {
            ans += i-1;
            cnt0 += 1;
            continue;
        }
        int a = 1;
        for (auto [k,v] : factor(A)) {
            if (v % 2) a *= k;
        }
        ans += cnt[a] + cnt0;
        cnt[a] += 1;
    }
    cout << ans << "\n";
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    while (t--) solve();
    return 0;
}