abc 342 D

筛质数，如果所有质数的指数奇偶性都相同，说明为同一种数，同一种数相乘是平方数
本来想用一种二进制的方法标记，但发现质数实在是很多，远多于64位（2 ~ 1e5 是9592个， 2 ~ 2E5 17984 个），所以失败了
（不过多个质数的乘积生成的数也是一个独特的数）
再特判一下 0 乘以其它数的情况就是答案

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

vector<ll> primes, minp;

void sieve(ll n) {
    minp.assign(n + 1, 0);
    primes.clear();

    for (ll i = 2; i <= n; i ++) {
        if (minp[i] == 0) {
            minp[i] = i;
            primes.push_back(i);
        }

        for (auto p : primes) {
            if (p > n / i) {
                break;
            }
            minp[i * p] = p;
            if (p == minp[i]) break;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; i ++) cin >> a[i];

    sieve(2E5);
    ll cnt = 0;

    vector<ll> b(n);
    for (int i = 0; i < n; i ++) {
        if (a[i] == 0) {
            a[i] = -1;
            cnt ++;
            continue;
        }

        for (int j = 0; primes[j] <= a[i] / primes[j]; j ++) {
            while (a[i] % (primes[j] * primes[j]) == 0) {
                a[i] /= primes[j] * primes[j];
            }
        }
    }

    ll ans = 0;
    map<int, int> tj;

    for (int i = 0; i < n; i ++) {
        ans += tj[a[i]] ++;
    }

    ans += (n - cnt) * cnt;

    cout << ans << endl;

    return 0;
}

abc 341 D

int lcm = lcm(n, m) // n 和 m 的最小公倍数 
用二分查找答案 x，要求是 x / n + x / m + x / lcm(n, m) * 2 >= k 的左边界