[ABC342D] Square Pair 题解

2c_s · 2024-02-25 08:31:41 · 题解

题目传送门

思路

这题本质是质因数分解。

假设我们有一个数，质因数分解出来是 a\times a\times b；另外一个数分解出来是 b\times c\times c。不难发现这两个数相乘的结果是 a^2\times b^2\times c^2，是 abc 的平方。

所以我们可以统计每个数质因数分解后有奇数个的因子之积。如果两个数奇数个因子之积相同，那么这两个数相乘一定是一个平方数（如上面给出的例子）。这个积的数量 k 的贡献为

但是由于 0\le A_i\le 2\times 10^5\space(1\le i\le N)，我们需要特殊考虑 A_i=0 的情况。此时数列中任何一个数 A_j\space(j\not=i) 和 A_i 相乘均为平方数。由于我们要保证相乘的两个数不能重复计算（如 (0,4) 和 (4,0) 应算作一对），所以还要每次减去当前已访问过的 0 的个数。

我们设每个非零数的贡献值为 k_i 且总共有 m 个非零数（去重后），0 的个数为 num，则最终答案为：

• 记得开 long long。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll read(){//快读
    ll k=0,flag=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')flag=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        k=(k<<1)+(k<<3)+(c^48);
        c=getchar();
    }
    return k*flag;
}
const int N=2e5+10;
int n,cnt,p[N],x[N],h[N];//h 数组是这个数处理完后的结果。
ll ans,cnt0,tom[N];
bool vis[N];
int main(){
    cin>>n;
    vis[1]=1;
    for(int i=2;i<=(int)2e5;++i){//处理出质数。
        if(!vis[i])p[++cnt]=i;
        for(int j=1;j<=cnt&&i*p[j]<=(int)2e5;++j){
            vis[i*p[j]]=1;
            if(i%p[j]==0)break;
        }
    }
    for(int i=1;i<=n;++i){
        x[i]=read();
        if(!x[i]){//0 的特判。
            ++cnt0;
            continue;
        }
        int t=x[i],tmp=1;
        if(h[x[i]]){//优化：访问过直接记录。
            ++tom[h[x[i]]];
            continue;
        }
        for(int j=1;j<=cnt;++j){//分解质因数。
            if(p[j]>t)break;//优化：大于当前值的质数不可能整除。
            if(t&&t%p[j]==0){
                int num=0;
                while(t&&t%p[j]==0){
                    t/=p[j];
                    ++num;
                }
                if(num&1)tmp*=p[j];
            }
        }
        ++tom[tmp];
        h[x[i]]=tmp;
    }
    memset(vis,0,sizeof vis);
    for(int i=1;i<=n;++i){
        if(vis[h[x[i]]])continue;
        ll k=tom[h[x[i]]];
        vis[h[x[i]]]=1;//标记重复。
        ans+=k*(k-1)/2;//计算非零数的贡献。
    }
    ans+=n*cnt0-cnt0*(cnt0+1)/2;//计算 0 的贡献。
    cout<<ans;
    return 0;
}

AC 记录