CF1225D Power Products

CF1225D Power Products

更好的阅读体验请戳这里

题意：

给你(n)个正整数(a_i (a_i leqslant 10^5))和一个整数(k(k>2))，请计算出有序数对((i,j)),(1 leqslant i < j leqslant n)，
并且存在整数(x)，满足(a_i*a_j=x^k)，

解析：

对于质数(p)，如果(p^a imes p^b = x^k) ，则 (a+b equiv 0 (modk)),即
(a equiv k-b (mod k))

设(a)分解质因数后为 (p_1^{c_1} imes p_2^{c_2} imes p_3{c_3} imes ...)

记 (f(a) = prod p_1^{c_1 mod k} imes p_2^{c_2 mod k} imes p_3{c_3 mod k} imes ...)

记 (g(a) = prod p_1^{(k-c_1 mod k)mod k} imes p_2^{(k-c_2 mod k)mod k} imes p_3{(k-c_3 mod k)mod k} imes ...)

对于每一个(a_i)直接暴力分解质因数，然后开一个桶统计(f(a_j)=g(a_i)),且 (j<i) 的(j)的个数，再把 (f(a_i))处+(1)即可

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <cctype>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;

#define inf 0x3f3f3f3f
typedef long long LL;
#define cls(x) memset(x,0,sizeof(x))
#define For(i,j,k) for(register int i=(j);i<=(k);++i)
#define Rep(i,j,k) for(register int i=(j);i>=(k);--i)
#define rint register int
#define il inline

il int read(int x=0,int f=1,char ch='0')
{
    while(!isdigit(ch=getchar())) if(ch=='-') f=-1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    return f*x;
}

const int N=2e5+5,L=1e5;
int a[N],v[N];
LL f,g;
int n,k,m;
il LL qpow(LL x,LL y) 
{
    LL ret=1; 
    for(;y;y>>=1) 
    { if(y&1) ret*=x; x*=x; if(ret>L||x>L) return 0; } 
    return ret; 
}

LL ans;
int main()
{
    n=read(); k=read();
    for(int i=1;i<=n;++i) a[i]=read();

    for(int i=1;i<=n;++i)
    {
        f=g=1;
        for(rint j=2;j*j<=a[i];++j) if(a[i]%j==0)
        {
            int c=0;
            while(a[i]%j==0) a[i]/=j,++c; c%=k;
            For(k,1,c) f*=j; c=(k-c)%k;
            for(int p=1;p<=c&&g;++p) g=g>L/j?0:g*j;
            //g>1e5的话就不可能产生贡献了，这里防止爆long long
        }
        if(a[i]>1)
        {
            int c=1;
            f*=a[i]; c=(k-c)%k;
            for(int p=1;p<=c&&g;++p) g=g>L/a[i]?0:g*a[i];
        }
        ans+=v[g]; ++v[f];
    }

    printf("%lld
",ans);
    return 0;
}