CF2275F Tea Blend 题解

· · 题解

考虑如何区。

首先完全平方数在拆质因数分解的时候，每个质因子的个数都是偶数。

我们对于一个数 x，定义 f(x) 表示 x 质因数分解后，质因数幂次为奇数的质因数的乘积。

那么我们在判断 a_i \times \prod_{k=1}^{j} a_k 是否为完全平方数的时候，只需要判断 f(a_i) 是否等于 f(\prod_{k=1}^{j} a_k) 即可。

后者扫一遍做，前者可以预处理。具体你怎么维护这个 f，可以随便 hash 一下，为了防止被卡我用了双哈希。

因为每个数不同的质因数数量非常少，所以这样做是不会 TLE 的。

代码写得很史，将就看吧 /kel。

::::success[code && submission]

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
#define _i128 __int128
using namespace std;
const int N = 2e5+5;
const int K = 1e6+5;
const LL up = 1000000;
const LL Bas1 = 29;
const LL Bas2 = 233;
const LL MOD1 = 998244353;
const LL MOD2 = 1e9+7;
int T,n,a[N];
pLL val[N];
int cnt,p[K],mnp[K],id[K];
LL q1[K],q2[K];
pLL sta;
LL t[K],Ans;
bool vis[K];
map<pLL,int> mp;
LL read(){
    LL su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}
void init(){
    vis[0]=1,vis[1]=1;
    cnt=0;
    for(LL i=2;i<=up;i++){
        if(!vis[i])
            p[++cnt]=i,id[i]=cnt,mnp[i]=i;
        for(int j=1;j<=cnt&&p[j]*i<=up;j++){
            vis[p[j]*i]=1;
            mnp[p[j]*i]=p[j];
            if(i%p[j]==0)continue;
        }
    }
    return;
}
void init_2(){
    q1[0]=1,q2[0]=1;
    for(int i=1;i<=cnt;i++)
        q1[i]=q1[i-1]*Bas1%MOD1,
        q2[i]=q2[i-1]*Bas2%MOD2;
    return;
}
pLL sol(LL num){
    LL now1=0,now2=0;
    while(num>1){
        LL x=id[mnp[num]],c=0;
        while(num%p[x]==0)num/=p[x],c^=1;
        now1=(now1+c*q1[x])%MOD1;
        now2=(now2+c*q2[x])%MOD2;
    }
    return {now1,now2};
}
void add(LL num){
    while(num>1){
        LL x=id[mnp[num]],c=t[x];
        sta.fr=(sta.fr-c*q1[x]%MOD1+MOD1)%MOD1;
        sta.se=(sta.se-c*q2[x]%MOD2+MOD2)%MOD2;
        while(num%p[x]==0)num/=p[x],t[x]^=1;
        c=t[x];
        sta.fr=(sta.fr+c*q1[x]%MOD1)%MOD1;
        sta.se=(sta.se+c*q2[x]%MOD2)%MOD2;
    }
    return;
}
void del(LL num){
    while(num>1){
        LL x=mnp[num],c=0;
        while(num%x==0)num/=x;
        t[id[x]]=0;
    }
    return;
}
int main(){
    T=read();init();init_2();
    while(T--){
        n=read();
        for(int i=1;i<=n;i++)a[i]=read();
        mp.clear();
        for(int i=1;i<=n;i++)
            val[i]=sol(a[i]),mp[val[i]]++;
        Ans=0,sta={0,0};
        for(int i=1;i<=n;i++)
            add(a[i]),Ans+=mp[sta];
        for(int i=1;i<=n;i++)del(a[i]);
        cout<<Ans<<"\n";
    }
    return 0;
}

::::

如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，真是太感谢啦！