0x01 大体思路

对于一个数，找到和它相乘符合题意的数有多少个，加入答案

0x02 简单推导

可以发现，设当前正处理的数为 $i$，将其分解质因数过后的结果为

$i = {p_1}^{x_1}{p_2}^{x_2}{p_3}^{x_3}...{p_t}^{x_t}$

符合与$i$配对的数$j$，当且仅当将$j$分解质因数后

$j = {p_1}^{y_1}{p_2}^{y_2}{p_3}^{y_3}...{p_t}^{y_t}$

对于每个质因数$p_i$，$x_i+y_i$为$k$的整数倍的时候，$i$与$j$成功配对

因为 $i * j = {p_1}^{x_1+y_1}{p_2}^{x_2+y_2}{p_3}^{x_3+y_3}...{p_t}^{x_t+y_t}$，此时$i*j$必为某数$X^k$

0x03 问题转化

现在的问题变为对于当前处理的$i$，如何找到符合0x02所提到的性质的数有多少个

但是要找对应质因数指数加起来为$k$倍数的，可能加起来为$k$的一倍，也可能两倍...等等很多情况

为了化简这样的问题，这里可以将每个数都分解质因数，然后将每个质因数的指数对$k$取个模，这样就相当于要找到有哪一些数$j$和当前的这个数$i$的对应质因数指数相加起来为$k$就行了。

0x04 实现过程

对于寻找符合要求的数$j$有多少个，这里可以采用的方法为哈希 + std::map

我们对每个数质因数指数情况做一次哈希，指数情况相同的数将得到相同的哈希值

我们使用std::map存储对应哈希值下有多少个数，然后从后往前处理每一个数

将每一个数分解质因数，边分解的同时，可以边计算出当前这个数$i$的哈希值xhash，以及符合与$i$匹配的$j$的哈希值aimhash。

最后，查找map里面是否有符合要求的$j$的哈希值aimhash，如果有，那么答案加上哈希值为aimhash的数的个数

最后在xhash的位置个数+1

0x05 代码

这里使用的是unsigned long long 自然溢出版本的哈希，$hashbase=2333$

# pragma G++ optimize "O2"
# pragma GCC optimize "O2"
# pragma G++ optimize "O3"
# pragma GCC optimize "O3"
# pragma G++ optimize "Ofast"
# pragma GCC optimize "Ofast"
#include <bits/stdc++.h>
#define LL(x) static_cast<long long>(x)
using namespace std;
#define rg register
typedef long long ll;
typedef unsigned long long ull;
inline int read(){
    rg char ch = getchar();
    register int ret = 0;
    while(!(ch >= '0' && ch <= '9')) ch = getchar();
    while(ch >= '0' && ch <= '9') ret = (ret << 3) + (ret << 1) + (ch ^ 48),ch = getchar();
    return ret;
}
int n,k;
const int maxn = 200010;
const int hashbase = 2333;
const int maxcnt = 60000;
int a[maxn];
int prime[maxn],cnt=0;
int primeid[maxn];
bool vis[maxn];
ull hashfac[maxn];
void initPrime(){
    vis[1] = 1;
    for(rg int i=2;i<100010;i++){
        if(!vis[i]) {
            prime[++cnt] = i;
            primeid[i] = cnt;
        }
        for(rg int j=1;j<=cnt;j++){
            if(prime[j] * i >= 100010) break;
            vis[prime[j] * i] = true;
            if(i % prime[j]) break;
        }
    }
}
void initHash(){
    hashfac[1] = hashbase;
    for(rg int i=2;i<=maxcnt;i++) hashfac[i] = hashfac[i-1] * hashbase;
}
map<ull,int> mp;
ll ans = 0;
void solve(int x){
    ull xhash = 0;
    ull aimhash = 0;
    int bakx = x;
    for(rg int i=1;i<=cnt;i++){
        if(x == 1) break;
        if(prime[i] * prime[i] > x) break;
        if(x % prime[i] == 0){
            int pcnt = 0;
            while(x % prime[i] == 0){
                x /= prime[i];
                pcnt++;
                if(pcnt >= k) pcnt -= k;
            }
            xhash += hashfac[i] * pcnt;
            if(pcnt != 0){
                aimhash += hashfac[i] * (k - pcnt);
            }
        }
    }
    if(x != 1){
        xhash += hashfac[primeid[x]];
        aimhash += hashfac[primeid[x]] * (k-1);
    }
    if(mp.count(aimhash)){
        ans += mp[aimhash];
    }
    mp[xhash]++;
}
int main(){
    n = read(),k = read();
    for(rg int i=1;i<=n;i++){
        a[i] = read();
    }
    initPrime();
    initHash();
    
    for(rg int i=n;i>=1;i--){
        solve(a[i]);
    }
    
    printf("%lld\n",ans);
    return 0;
}