cf 1225D - Power Products

https://codeforces.com/problemset/problem/1225/D
题意：给一些数，问满足下列条件的数对的数量，对于给定的 k， ∃ x , s . t .   a i ∗ a j = x k \exists x, s.t. \ a_i * a_j = x^k ∃x,s.t. ai​∗aj​=xk。
思路：容易想到分解质因数，再将指数都对于k取模，将所有的数都这样处理，称为化简。同时对于这些数剩下的质因数，我们可以根据 k 算得与之对应满足条件的 b[i], b[i] 的的质因数的指数和 a[i] 对应的质因数的指数相加为k，然后在其他数中找是否存在化简后的这样的数，及其个数。注意这里在计算的时候要考虑到所有a的大小不超过1e5， 所以在计算对应的b的时候，如果超过1e5就说明没有。（不然re一发）
over。

#include<bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

const int N = 1e5+10;

int p[N], cntp;
bool vis[N];

pii d[30];

int cnt[N];

int a[N];
int b[N];

int n, k;

void sieve(int n) {
    for(int i = 2; i < n; i++) {
        if(!vis[i]) p[cntp++] = i;
        for(int j = 0; j < cntp && p[j] <= n / i; j++ ){
            vis[p[j] * i] = 1;
            if(i % p[j] == 0) break;
        }
    }
}

void normalize(int idx) {
    int u = a[idx];
    int cntd = 0;
    for(int i = 0; i < cntp && u > 1; i++) {
        if(u % p[i] == 0){
            int cntt = 0;
            while(u % p[i] == 0) {
                u /= p[i];
                cntt++;
            }
            d[cntd++] = {p[i], cntt % k};
        }
    }
    if(u >= 1) d[cntd++] = {u, 1};
    u = 1;
    ll v = 1;
    for(int i = 0; i < cntd && v < N; i++) {
        if(d[i].second) {
            for(int j = 0; j < k - d[i].second && v < N; j++) 
                v *= d[i].first;
            
            for(int j = 0; j < d[i].second; j++) 
                u *= d[i].first;
        }
    }
    cnt[u]++;
    if(v < N) b[idx] = v;
    a[idx] = u;
}

int main() {
    sieve(1e3+10);
    scanf("%d%d", &n, &k);

    for(int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        normalize(i);
    }

    ll ans = 0;
    for(int i = 0; i < n; i++) {
        ans += cnt[b[i]];
        if(a[i] == b[i])  ans --;
    }
    ans >>= 1;
    printf("%lld\n", ans);
    return 0;
}

feel good, 自己想出来的题，但是想出来之后又觉得思路很简单， 不应该想这么久