思路非常好，写博客总结一下。

给你n个数与m，让你找出所有的对数

首先对于我们 任意的  我们都可以将其分解为：

如果两个数相乘等于 x的k次方，那么两个数质因子分解后会有两种情况：

1.两个数分解后的质因子相同，且各质因子的幂次相加后为m的倍数

2.两个数分解后的质因子不同，那么不相同的质因子数的幂次绝对为m的倍数

所以我们首先对每一个 ai 进行质因子分解，用一个数将ai的质因子幂次%m后再乘起来。用map存一下。

在对现在的数进行质因子分解，求出他需要的数。

用map遍历一遍O(n)即可。

说明:不同质因子，一定幂次是m的倍数，取余幂次后已经消失了。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
const ll mod=1e9+7;
const int maxn=1e6+5;
const int INF=1e9+7;
using namespace std;
const double eps=1e-8;
ll n,m;
int prime[maxn];
int vis[maxn];
ll num[maxn];
ll cnt=0;
map<ll,ll>mp;
ll a[maxn],b[maxn];
void restart(){
    vis[1]=1;
    for(int i=2;i<1005;i++){
        if(!vis[i]){
            prime[++cnt]=i;
            for(int k=i*2;k<1005;k+=i)
                vis[k]=1;
        }
    }
}
ll qpow(ll a,ll b)
{
    ll ans=1;
    while(b){
        if(b&1) ans=ans*a;
        b/=2;a=a*a;
    }
    return ans;
}

int main()
{
    restart();
    scanf("%lld%lld",&n,&m);mp.clear();
    for(int i=1;i<=n;i++) scanf("%lld",&num[i]);
    ll res=0;
    for(int i=1;i<=n;i++){
        ll temp=num[i];
        ll now=1;
        for(int k=1;k<=cnt;k++){
            int cot=0;
            while(temp%prime[k]==0)
            {
                temp/=prime[k];
                cot++;
            }
            cot%=m;
            if(cot) now=now*qpow(prime[k],cot);
        }
        if(temp>1)  now*=temp;
        a[i]=now;
        mp[a[i]]++;
        b[i]=1;
        for(int k=1;k<=cnt;k++){
            int cot=0;
            while(now%prime[k]==0)
            {
                now/=prime[k];
                cot++;
            }
            cot%=m;
            if(cot) b[i]=b[i]*qpow(prime[k],m-cot);

        }
        if(now>1) b[i]*=qpow(now,m-1);
        if(b[i]==a[i]) res+=mp[b[i]]-1;
        else res+=mp[b[i]];
    }
    printf("%lld\n",res);
    return 0;
}

另外此题还有一种特别骚的办法...,map存一下 vector.

AC:

#pragma GCC optimize(2)
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
const ll mod=1e9+7;
const int maxn=1e6+5;
const int INF=1e9+7;
using namespace std;
const double eps=1e-8;
ll n,m;
int prime[maxn];
int vis[maxn];
ll num[maxn];
ll cnt=0;
void restart(){
    vis[1]=1;
    for(int i=2;i<1005;i++){
        if(!vis[i]){
            prime[++cnt]=i;
            for(int k=i*2;k<1005;k+=i)
                vis[k]=1;
        }
    }
}
map<vector<pair<int,int>>,int>mp;
vector<pair<int,int>>v[100005];
vector<pair<int,int>>cop[100005];
int main()
{
    restart();mp.clear();
    scanf("%lld%lld",&n,&m);
    ll res=0;
    for(int i=1;i<=n;i++) scanf("%lld",&num[i]);
    for(int i=1;i<=n;i++){
        ll temp=num[i];
        for(int k=1;k<=cnt;k++){
            int cot=0;
            while(temp%prime[k]==0){
                temp/=prime[k];
                cot++;
            }
            cot%=m;
            if(cot){
                v[i].push_back(make_pair(prime[k],cot));
                cop[i].push_back(make_pair(prime[k],m-cot));
            }
        }
        if(temp>1){
            v[i].push_back(make_pair(temp,1));
            cop[i].push_back(make_pair(temp,m-1));
        }
        res+=mp[cop[i]];
        mp[v[i]]++;
    }
    printf("%lld\n",res);
    return 0;
}
/***
6 4
4 4 16 1 4 4
***/

总结：

别遇到对数就去二分了...多动脑子.

根号下分解质因数需要特判剩余数>1