题解：P10827 [EC Final 2020] Square

fede · 2024-08-05 16:26:53 · 题解

前言

各位大佬写的题解稍稍有些有些简短，有些细节没有点到（看不到我），特来发篇题解(〃´-ω･)

此外，向管理员大大致歉，因对LaTeX使用不太熟练与未能对题解进行检查，一不小心添加了多余的积分符号（现已更正），造成还需管理员大大重新审核的严重后果，在此庄重宣布：
管理员大大，对不起！我错了！○|￣|_

正文

分析

首先简单理解一下题意：

创造一个 t 序列，对于每个 i~(1\le i<n) 满足 a_i\times t_i\times a_{i+1}\times t_{i+1} 为完全平方数，求出序列 t 中所有值的乘积最小(\prod_{i=1}^{n}{t_i})。

设完全平方数为 x，则一定可以写成 x=y^2 的形式。
对 y 进行质因子分解，设指数为 k，可以写成

可得

若 k 为奇数，则 k+k 为偶数，若 k 为偶数，则 k+k 为偶数。

由此得出结论，完全平方数的质因子分解的每项指数都为偶数。

把 a_i*a_{i+1} 看成一个整体 b_i。
如果 b_i 要变成完全平方数，则一定要让 b_i 的所有质因子的指数变为偶数，所以序列 t 要做的就是为 b_i 乘上指数为奇数的质因子。

对每个 a_i 分解质因数，记录每个质因数的指数，如果指数为奇数，则 a_i 需要乘上这个质因数。
但是有一个问题，a_i 乘上数是会影响 a_{i-1} 的，每个 a_i 都乘上质因子，答案不会最优。

因为只要知道 \prod_{i=1}^{n}{t_i}，考虑对每个出现过的质因数分开讨论，统计好质因数指数为奇数的次数（好绕）。

设 cnt_{i} 表示质因数 i 指数为奇数的次数，两种可能：

• 如果质因数 i 的指数都为偶数，则 cnt_{i} 为 0，此时不用做任何操作。
• 如果质因数 i 的指数有为奇数的，则 cnt_{i} 不为 0，此时有两种选择：一、将所有质因数 i 的指数为奇数的数都乘上质因数 i，让质因数 i 的指数都为偶数；二、将所有质因数 i 的指数为不为奇数的数都乘上质因数 i，让所有数都有质因数 i 并将质因数 i 的指数都为奇数。

嗯 (⊙o⊙)… 。非常抽象，我们设 ans 表示 \prod_{i=1}^{n}{t_i} ，再做一个详细的剖析：

对于第一种可能，简单直白，不做任何操作，ans 不变。

对于第二种可能，举个栗子
我们假设 a 序列有数 2,3,6,9:
对于质因数 2，2 有质因数 2 且指数为 1（奇数），6 有质因数 2 且指数为 1（奇数），所以 cnt_2 为 2；
对于质因数 3，3 有质因数 3 且指数为 1（奇数），6 有质因数 3 且指数为 1（奇数），9 有质因数 3 且指数为 2（偶数），所以 cnt_3 为 2。
为了将 2\times 3、 3\times 6、 6\times 9 变为完全平方数，我们可以给 2 乘上质因数 2，给 3 乘上质因数 3，给 6 乘上质因数 2 和 3，所得答案为 36。

我们再假设 a 序列有数 2,3,6,8:
对于质因数 2，2 有质因数 2 且指数为 1（奇数），6 有质因数 2 且指数为 1（奇数），所以 cnt_2 为 2；
对于质因数 3，3 有质因数 3 且指数为 1（奇数），6 有质因数 3 且指数为 1（奇数），8 有质因数 2 且指数为 3（奇数），所以 cnt_3 为 2。
为了将 2\times 3、 3\times 6、 6\times 8 变为完全平方数，我们可以给 2 乘上质因数 2，给 3 乘上质因数 3，给 6 乘上质因数 2 和 3，给 8 乘上质因数 2，所得答案为 72，但显然不是最优。
为了最优，我们还可以给 2 乘上质因数 3，给 3 乘上质因数 2，给 8 乘上质因数 3，所得答案为 18。

有质因数2指数为奇数的数有 2、6、8，为了变为完全平方数，这些数都得乘上质因数 2，但最优解却是给 3 乘上质因数 2，这是为什么呢？

可以这么做的原因是 a_i 势必会影响到 a_{i-1}，所以说如果 a_i 质因数p的指数为奇数，且 a_{i-1} 质因数 p 的指数也为奇数，那么两者相乘积的质因数 p 的指数一定为偶数，也可以达到我们需要的要求，但答案 b 序列所以值都是有关联的，因此要么质因数 p 指数为奇数的数都乘 p，要么让所有质因数 p 指数不为奇数的数(包括没有质因数 p）都乘 p。

思路

开始的时候预处理好范围内所有数分解出来的质因子的指数，放进 \operatorname{map} 里，可以选择埃氏筛法，好理解又好写，时间复杂度为 O(n\log n)。

之后，对于每个输入的 a_i，从 \operatorname{map} 里取出质因数 p 和对应的指数，如果指数为奇数，cnt_p 增加 1。

然后，我们再遍历所有的质因数，如果指数都为偶数或没有出现，也就是 cnt_p=0，那么找下一个出现过的质因数；否则考虑两种选择，将所有质因数 p 指数为奇数的数都乘 p，也就是 ans=ans\times p^{cnt_p}，或者将所有质因数 p 指数不为奇数的数(包括没有质因数 p）都乘 p，也就是 ans=ans\times p^{n-cnt_p}。

最后，输出答案 ans，此题拿下。

代码

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e6+10;
const int mod=1e9+7;
int n,ans=1;
int a[N],cnt[N];
map<int,int> mp[N];
bool isp[N];
int ksm(int a,int b,int c){
    if(b==0) return 1%c;
    if(b==1) return a%c;
    int t=ksm(a,b/2,c);
    if(b%2==0) return t*t%c;
    return t*t%c*a%c;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    for(int i=2;i<=1e6;i++){
        if(isp[i]){
            continue;
        }
        for(int j=i;j<=1e6;j+=i){
            isp[j]=1;
            int x=j;
            while(x%i==0){
                mp[j][i]++;
                x/=i;
            }
        } 
        isp[i]=0;
    }
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        for(map<int,int>::iterator it=mp[a[i]].begin();it!=mp[a[i]].end();it++){
            int x=it->first,y=it->second;
            if(y%2!=0){
                cnt[x]++;
            }
        }
    }
    for(int i=2;i<=1e6;i++){
        if(isp[i]){
            continue;
        }
        if(cnt[i]!=0&&cnt[i]<n){
            ans=ans*ksm(i,min(cnt[i],n-cnt[i]),mod)%mod;
        }
    }
    cout<<ans<<endl;
    return 0;
}

时间复杂度 O(n\log n)，空间复杂度 O(n\log n)，完美通过此题。