https://codeforces.com/problemset/problem/1225/D
You are given nn positive integers a_1, \ldots, a_na1,…,an , and an integer k \geq 2k≥2 . Count the number of pairs i, ji,j such that 1 \leq i < j \leq n1≤i<j≤n , and there exists an integer xx such that a_i \cdot a_j = x^kai⋅aj=xk .
The first line contains two integers nn and kk ( 2 \leq n \leq 10^52≤n≤105 , 2 \leq k \leq 1002≤k≤100 ).
The second line contains nn integers a_1, \ldots, a_na1,…,an ( 1 \leq a_i \leq 10^51≤ai≤105 ).
Print a single integer — the number of suitable pairs.
现在给你nn个正整数 [a_1,a_2,...,a_n][a1,a2,...,an] 和一个的正整数k\geq2k≥2，现在请你求出有多少组 (i,j)(i,j) ，满足 (1≤i<j≤n)(1≤i<j≤n)且存在一个整数 xx 满足 a_i\times a_j=x^kai×aj=xk
输入第一行是两个正整数nn和kk(2≤n≤10^5,2≤k≤100)(2≤n≤105,2≤k≤100)
第二行为nn个正整数[a_1,a_2,...,a^n](1≤a_i≤10^5)[a1,a2,...,an](1≤ai≤105)
输出一个整数，表示有多少满足条件的组合
样例中有以下几组满足条件的组合
a_1*a_4=8=2^3a1∗a4=8=23
a_1*a_6=1=1^3a1∗a6=1=13
a_2*a_3=27=3^3a2∗a3=27=33
a_3*a_5=216=6^3a3∗a5=216=63
a_4*a_6=8=2^3a4∗a6=8=23
一共五组，所以输出为55
输入 #1复制
6 3 1 3 9 8 24 1输出 #1复制
5In the sample case, the suitable pairs are:
a_1 \cdot a_4 = 8 = 2^3a1⋅a4=8=23 ;a_1 \cdot a_6 = 1 = 1^3a1⋅a6=1=13 ;a_2 \cdot a_3 = 27 = 3^3a2⋅a3=27=33 ;a_3 \cdot a_5 = 216 = 6^3a3⋅a5=216=63 ;
暴力的思路沿呈https://blog.csdn.net/zstuyyyyccccbbbb/article/details/108357803
式子转化一下可以得到
但是k==2的时候，预处理的数字个数有1e5个，然后去处理就超时了。（TLE6）
这题有一个结论：两个数的积为 k 次方数，当且仅当每一质因子的次数和都是 k 的倍数。
证明：把两个数分别个分解质因数了。
A=p1^k1*p2^k2*p3^k3....pn^kn;
B=p1^c1*p2^c2*p3^c3.....pn^cn;
对于每个质因数pi,ki+ci为k的整数倍的时候,i与j成功配对
因为i*j=p1^(k1+c1)*p2^(k2+c2)*.....pt^(kt+ct)
此时i*j必为X^k.
那么只有k==2TLE，我们特判k==2的时候。k==2的时候，也就是i*j的每个质因数pi的次数(ki+ci)为2的整数倍。也就是只有在ki和ci同时为奇数或者偶数的时候才成立。
那先预处理1e5以内的质因子，然后对每个a[i]质因数分解，用bitset维护每个a[i]每个质因数出现的次数。然后把bitset存到unordered_map里，查询的时候查里面同奇偶的map[bitset]
#include<iostream> #include<vector> #include<queue> #include<cstring> #include<unordered_map> #include<cmath> #include<map> #include<bitset> #include<set> #include<cstdio> #include<algorithm> #define debug(a) cout<<#a<<"="<<a<<endl; using namespace std; const int maxn=1e5+100; typedef long long LL; const int cntp=1e4;//质数个数 LL n,k1,a[maxn]; LL v[maxn],primes[maxn];//v[i]存的是i的最小质因子,primes[m]里面存筛出来的质数 map<LL,LL>map1; unordered_map<bitset<cntp>,LL>mp; LL x[maxn]; LL m=0;//质数个数 inline LL ksm(LL x,LL a){ LL ret=1,k=x; for (;a;a>>=1,k=k*k) if (a&1) ret=ret*k; return ret; } void getprimes(int n) { //memset(v,0,sizeof(v));//最小质因子 for(LL i=2;i<=n;i++) { if(v[i]==0) {v[i]=i;primes[++m]=i;}//i是质数 //给当前的数i乘上一个质因子 for(LL j=1;j<=m;j++) { //i有比primes[j]更小的质因子，或者超出n的范围，停止循环 if(primes[j]>v[i]||primes[j]>n/i) break; //primes[j]是合数i*primes[j]的最小质因子 v[i*primes[j]]=primes[j]; } } //for(LL i=1;i<=m;i++) cout<<primes[i]<<endl; } int main(void) { cin.tie(0);std::ios::sync_with_stdio(false); cin>>n>>k1; for(LL i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+1+n); if(k1==2) { LL ans=0; getprimes(100000); bitset<cntp>b; for(LL i=1;i<=n;i++){ b.reset();//全置0 b.set(0);//第0位置赋1 LL tmp=a[i]; LL cnt=0; for(LL j=1;j<=m;j++) { while(tmp%primes[j]==0){ ++cnt;tmp/=primes[j]; } if(cnt&1) b.set(j); cnt=0; if(tmp==1) break; } ans+=mp[b]; mp[b]++; } cout<<ans<<endl; } else { LL pos=1;//用set TLE11 for(LL i=1; ;i++) { x[i]=ksm(i,k1); if(x[i]>=1e10) { pos=i;break; } } LL ans=0; //枚举右端 for(LL i=1;i<=n;i++) { ans+=map1[a[i]]; for(LL j=1;j<=pos;j++) { if((x[j])%a[i]==0) { map1[x[j]/a[i]]++; } } } cout<<ans<<endl; } return 0; }
