题目链接 https://www.acwing.com/problem/content/4322/

数论题 先留着以后看

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010;

int n, k;
int cnt[N];

LL power(int x, int s)
{
    LL res = 1; //不用LL会爆int 
    while(s--)
    {
        res *= x;
        if(res >= N)    //如果结果大于N（不满足题意），说明没有意义
        {
            res = 0;
            break;
        }
    }
    return res;
}

int main()
{
    int num;
    LL p, con_p, res = 0;
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &num);
        p = 1, con_p = 1;   
        for(int i = 2; i*i <= num; i++) //先分解因式
        {
            if(num%i == 0)  //若i是num的因子
            {
                int s = 0;  //i的阶数
                while(num%i == 0)   //求i的阶数
                {
                    s++;
                    num /= i;
                }
                s %= k; //我们需要的是s除以k的余数
                if(s)
                {
                    p *= power(i, s);   //不会大于N，因为p是num的因子，而num < N
                    con_p *= power(i, k-s); //若太大则没意义，会返回0
                }
            }
        }
        if(num > 1)   //因式分解后还是大于1，说明是质数
        {
            p *= pow(num,1);
            con_p *= power(num, k-1);
        }
        if(con_p >= N)  //若是“互补”的数大于n，则没有意义
            con_p = 0;
        res += cnt[con_p];
        cnt[p]++;
    }
    printf("%lld", res);    //记得输出long long类型要用%lld 
    return 0;
}