daimayuan 733. 合适数对

题意：

给定一个长度为 nn 的正整数数列 a1,a2,…,an 和一个正整数 k。问共有多少个数对 (l,r) 同时满足：

• 1≤l
• 存在一个整数 x 使得 \(a_l\times a_r=x^k\) 成立

\(n\le 1e6,2\le k \le 100, 1\le a_i\le 1e7\)

思路：

https://zhuanlan.zhihu.com/p/497036128

只需要筛最小质因子的话，筛的时候还可以跳过偶数之类的，因子分解的时候偶数就是2

const signed N = 1e7 + 3, M = 1e7;
int n, k, mp[N]; ll ans;

int minp[N], pr[N], tot;
void getPri(int n) {
    minp[1] = 1;
    for(int i = 2; i <= n; i++) {
        if(!minp[i]) minp[i] = i, pr[++tot] = i;
        for(int j = 1; pr[j] * i <= n; j++) {
            minp[i * pr[j]] = pr[j];
            if(minp[i] == pr[j]) break;
        }
    }
}

ll qmi(ll x, ll k) {
    ll res = 1;
    for(; k; k >>= 1) {
        if(k & 1) res *= x;
        x *= x;
        if(res > M) return 0;
    }
    return res;
}

void fenjie(int x) {
    ll p = 1, q = 1;
    while(x > 1) {
        int d = minp[x], cnt = 0;
        while(x % d == 0)
            x /= d, (cnt += 1) %= k;
        p *= qmi(d, cnt); //次数范围是[0,k)
        if(cnt) q *= qmi(d, k - cnt);
        if(q < 0 || q > M) q = 0;
    }
    ans += mp[q];
    mp[p]++;
}

signed main() {
    iofast;
    getPri(M);
    cin >> n >> k;
    for(int i = 1, x; i <= n; i++)
        cin >> x, fenjie(x);
    cout << ans;
}