power products
解题思路：
tle思路：计算出每个值出现的次数，然后枚举x ，因为我看乘机最大也才1e10嘛 ，但是不行，当k=2的时候会卡，别的情况应该不会。哎，，
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
const int N=100010;
ll a[N];
const int mod = 998244353;
map<ll,int>mp;
ll qmi(ll a,int b)
{
ll res=1;
while(b)
{
if(b&1) res=res*a;
a = a*a;
b>>=1;
}
return res;
}
int main()
{
int n,k;
cin>>n>>k;
ll maxv=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
mp[a[i]]++;
maxv=max(maxv,a[i]);
}
ll res=0;
ll ans2=0;
for(int i=1;;i++)
{
ll tt=qmi(i,k);
if(tt>maxv*maxv) break;
for(auto it:mp)
{
ll z = it.first;
ll y = it.second;
if(tt%z==0)
{
ll zz = tt/z;
if(zz!=z)
res+=y*mp[zz];
else
ans2+=mp[zz]*(mp[zz]-1)/2;
}
}
}
cout<<res/2 + ans2 <<endl;
return 0;
}
正确思路：我看了一个用哈希解决的方法，将所有数质因数分解，如果乘积是x的k次，那么他们每个质因数的幂一定是k的整数倍，我们将每个质因数的次数哈希，然后开一个bhash用来计算和它相补的值，最后用个map来查询bash哈希值对应的次数，最后加起来就是答案。
/*#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
const int N=100010;
ll a[N];
const int mod = 998244353;
map<ll,int>mp;
ll qmi(ll a,int b)
{
ll res=1;
while(b)
{
if(b&1) res=res*a;
a = a*a;
b>>=1;
}
return res;
}
vector<ll>Q;
int main()
{
int n,k;
cin>>n>>k;
ll maxv=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
mp[a[i]]++;
maxv=max(maxv,a[i]);
}
ll res=0;
ll ans2=0;
for(int i=1;;i++)
{
ll tt = qmi(i,k);
if(tt>maxv * maxv) break;
Q.push_back(tt);
}
for(int i=0;i<Q.size();i++)
{
ll tt=Q[i];
if(tt>maxv*maxv) break;
for(auto it:mp)
{
ll z = it.first;
ll y = it.second;
if(z*z>tt) break;
if(tt%z==0)
{
ll zz = tt/z;
if(zz!=z)
res+=y*mp[zz];
else
ans2+=mp[zz]*(mp[zz]-1)/2;
}
}
}
cout<<res + ans2 <<endl;
return 0;
}*/
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
const int N=100010;
ll a[N];
const int mod = 998244353;
typedef unsigned long long ull;
ull base = 131;
ull Hash[N];
int prime[N];
int cnt;
bool st[N];
int n,k;
int primeid[N];
void init()
{
for(int i=2;i<N;i++)
{
if(!st[i])
{
primeid[i]=cnt;
prime[cnt++]=i;
}
for(int j=0;i*prime[j]<=N-1;j++)
{
if(i%prime[j]==0) break;
st[i*prime[j]]=true;
}
}
}
map<ull,int>mp;
ll qmi(ll a,int b)
{
ll res=1;
while(b)
{
if(b&1) res=res*a;
a = a*a;
b>>=1;
}
return res;
}
int work(int u)
{
ll p = a[u];
ull xhash=0;
ull bhash=0;
for(int i=0;i<cnt;i++)
{
if(prime[i]*prime[i]>p) break;
if(p%prime[i]==0)
{
int pcnt=0;
while(p%prime[i]==0)
{
p/=prime[i];
pcnt++;
if(pcnt>=k)
pcnt-=k;
}
xhash+=pcnt*Hash[i+1];
bhash+=((k-pcnt)%k+k)%k*Hash[i+1];
}
}
if(p!=1)
{
xhash+=1*Hash[primeid[p]+1];
bhash+=(k-1)*Hash[primeid[p]+1];
}
ll res=mp[bhash];
mp[xhash]++;
return res;
}
int main()
{
cin >> n >> k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
Hash[0]=1;
init();
//cout<<cnt<<endl;
for(int i=1;i<cnt;i++)
Hash[i]=Hash[i-1]*base;;
ll res=0;
for(int i=n;i>=1;i--)
res+=work(i);
cout<<res<<endl;
return 0;
}
查看14道真题和解析
