自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:26:33，当前版本为作者最后更新于2020-11-23 22:43:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

• Update on 2023.4.4 勘误：$g_i$ 实际上等于 $d_i$ 质因子数量的两倍减去 $1$。

题目传送门。

---

首先将 $n$ 分解质因数，用 DFS 求出 $n$ 的所有因数，记为 $d_1,d_2,\cdots,d_c$，跑一遍反素数那题的代码可知 $c\leq 23327$（

设 $f_i$ 表示根节点为 $d_i$ 时最小值。

显然，局部最优值可以保证整体最优值，且转移无后效性，即求 $f_i$ 时不会影响 $f_j\ (d_j<d_i)$，故答案可以用树形 DP 求出，将所有因数排序后可以转化为序列上的 DP。

对于不能出现在树上的 $d_i$ 直接 skip 即可。

设 $g_i$ 表示 $d_i$ 所含有的质因子个数。For example，$12=2\times 2\times 3$，所以 $12$ 有 $3$ 个质因子。在本题中，$g_{i}$ 也表示以 $d_i$ 为根的子树的节点个数，不难发现其为定值。

假设当前转移 $f_i$ 决策点为 $j,k\ (d_j\times d_k=d_i)$，那么对于 $d_j$ 和 $d_k$ 子树内两两组合出的 pairs 的贡献可以直接由 $f_j+f_k$ 推得，剩下来只有两种情况：

• Case 1：$d_j$ 和 $d_k$ 子树内各一个节点组合出的 pairs。因为它们的 LCA 是 $d_i$，且共有 $g_j\times g_k$ 对 pairs，故贡献为 $g_j\times g_k\times d_i$。
• Case 2：$d_i$ 和任意一个节点组合出的 pairs。显然贡献为 $g_i\times d_i$。

转移方程：

$$f_i=\min_{d_j\times d_k=d_i}f_j+f_k+(g_j\times g_k+g_i)\times d_i $$

其中 $g_i=g_j+g_k+1$ 可以在 DP 时一并求出。

这样子搞是 $\mathcal O(c^3)$ 的，显然无法接受。

• 剪枝 1：在枚举内层循环 $j$ 时发现 $k$ 有单调性，所以直接用指针代替 $k$ 即可。这样时间复杂度降为了 $\mathcal O(c^2)$。
• 剪枝 2：当 $j>k$ 时直接 break，减小常数。

综上，我们有了一个 ${\mathcal O}(\sqrt n+m\log c+c^2)$ 的算法（分解质因数 + 处理限制需要二分查找 + DP），代码如下：

ll n,m,num[N],f[N];
ll cnt,pr[N],c[N],tot;
ll fc[N],il[N],d;
map <ll,int> isp;

void dfs(int pos,ll prod){
	if(pos>cnt){
		if(prod>1)fc[++d]=prod;
		return;
	} for(int i=0;i<=c[pos];i++)dfs(pos+1,prod),prod*=pr[pos];
}

int main(){
	
	cin>>n>>m;
	// factor
	ll tmp=n;
	for(ll i=2;i*i<=n;i++)
		if(n%i==0){
			pr[++cnt]=i,isp[i]=1;
			while(n%i==0)c[cnt]++,tot++,n/=i;
		}
	if(n>1)pr[++cnt]=n,tot++,c[cnt]=1,isp[n]=1;
	n=tmp;
	
	// find factors
	dfs(1,1);
	sort(fc+1,fc+d+1);
	
	// limit
	for(int i=1;i<=m;i++){
		ll val=read();
		int pos=lower_bound(fc+1,fc+d+1,val)-fc;
		if(pos<=d&&fc[pos]==val)il[pos]=1; // 表示 pos 不能出现
	}
	
	// dp
	for(int i=1;i<=d;i++){
		if(il[i])continue;
		if(isp[fc[i]]){
			num[i]=1,f[i]=fc[i];
			continue;
		} il[i]=1,f[i]=inf; // 如果无法由以前的 j,k 转移得到那么 i 也无法得到
		int p=i-1;
		for(int j=1;j<i;j++){
			if(fc[i]%fc[j])continue;
			while(fc[p]>fc[i]/fc[j])p--;
			if(j>p)break;
			if(!il[j]&&!il[p])f[i]=min(f[i],f[j]+f[p]+num[j]*num[p]*fc[i]+(num[i]=num[j]+num[p]+1)*fc[i]),il[i]=0;
		}
	} if(il[d])puts("-1");
	else cout<<(ll)f[d]<<endl;
	return 0;
}