自动搬运

查看原文

来自洛谷，原作者为

	fede 我不去想是否能够成功，既然选择了远方，便只顾风雨兼程；我不去想身后会不会袭来寒风冷雨，既然目标是地平线，留给世界的只能是背影。

搬运于2025-08-24 23:01:38，当前版本为作者最后更新于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$，可以写成

$$\textstyle y=P_1^{k_1}\times P_2^{k_2}\times P_3^{k_3}\times … $$

可得

$$\textstyle x=y^2=(P_1^{k_1}\times P_2^{k_2}\times P_3^{k_3}\times …)^2 $$$$\textstyle =(P_1^{k_1}\times P_1^{k_1})\times (P_2^{k_2}\times P_2^{k_2})\times (P_3^{k_3}\times P_3^{k_3})\times … $$$$\textstyle =P_1^{k_1+k_1}\times P_2^{k_2+k_2}\times P_3^{k_3+k_3}\times … $$

若 $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)$，完美通过此题。