P10827 [EC Final 2020] Square 题解

· · 题解

题意简述

有一个数组 a_1,a_2,a_3,...,a_n，求出乘积最小的 t 数组 t_1,t_2,t_3,...t_n 使得对于每个 i (1\le i<n), a_i\times t_i\times a_{i+1}\times t_{i+1} 是完全平方数。

Sol

明显对于每个 a_i\times t_i 其因数的出现次数只有两种情况：都是奇数或都是偶数。

对这两种情况分别计算，取最小值即可。

Code

//签到
//TEAM_NAME:CYX&LSY AK ICPC
//Problem B
//By CYX
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
bool isprime[1000005];
int pri[1000005],s[1000005],vis[1000005],num[1000005],prime[1000005],cnt,tot;
void init(){
    s[1]=1;
    for(int i=2;i<=1000005;i++){
        if(!isprime[i])prime[++cnt]=i,s[i]=i;
        for(int j=1;j<=cnt;j++){
            if(i*prime[j]>1000005)break;
            isprime[i*prime[j]]=1;
            s[i*prime[j]]=prime[j];
            if(!(i%prime[j]))break;
        }
    }
}
int qpow(int a,int b){
    int ans=1;
    while(b){
        if(b&1)ans=ans*a%1000000007;
        a=a*a%1000000007;
        b>>=1;
    }
    return ans;
}
signed main(){
    init();
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;cin>>x;
        tot=0;
        while(x>1){
            if(!vis[s[x]])pri[++tot]=s[x];
            vis[s[x]]++;
            x/=s[x];
        }
        for(int j=1;j<=tot;j++){
            if(vis[pri[j]]%2==1)num[pri[j]]++;
            //num是指数为奇数的质因子的出现次数
            vis[pri[j]]=0;
        }
    }
    int ans=1;
    for(int i=1;i<=cnt;i++){
        if(!num[prime[i]])continue;
        ans*=qpow(prime[i],min(num[prime[i]],n-num[prime[i]]));
        ans%=1000000007;
    }
    cout<<ans;
    return 0;
}