自动搬运

查看原文

来自洛谷，原作者为

	Unnamed114514 祈祷着今后的你的人生，永远都有幸福的「魔法」相伴。

搬运于2025-08-24 22:49:54，当前版本为作者最后更新于2023-08-28 18:36:27，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

验题人题解。

讲个笑话，出题人最早打的是 $O(nm)$，还被 ddxrS 叉了。

然后在一阵口胡之下成了第一发正解。

如果正向求所有情况的最小次数，很难处理，于是考虑枚举每一种情况然后求这一种情况的最小次数。

考虑枚举最后所有数都变成的数 $D$，那么就会有 $D\mid \min\{A\}$，当然如果存在 $i$ 使得 $D\nmid A_i$ 的情况除外。

那么现在就是求 $\sum\limits_{i=1}^n step(A_i\to D)$。

那么对于 $A_i$，我们相当于要除以一个 $x=\dfrac{a_i}{D}$，问题就转化为了 $B$ 中子序列乘积为 $x$ 的最短长度。

那么问题就转化为了一个背包，如果直接背包，复杂度是 $O(n^2)$ 级别的，考虑优化。

若存在 $i,j$ 使得 $B_i=B_j$，那么 $i,j$ 就是等价的，于是对 $B$ 去个重。

那么这个时候时间复杂度就是 $O(n+\dfrac{n}{2}+\cdots+\dfrac{n}{m})$，是一个调和级数，那么整体的时间复杂度就是 $O(n\log n)$。

讲个笑话，这个题原数据甚至不去重或者不 sort 直接 unique 都能过。

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
const int N=5e5+5;
int n,m,ans=inf,a[N],b[N],V,dp[N];
inline int get(int x){
	int s=0;
	for(int i=1;i<=n;++i){
		if(a[i]%x)
			return inf;
		if(dp[a[i]/x]==inf)
			return inf;
		s+=dp[a[i]/x];
	}
	return s;
}
signed main(){
	ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i)
    	cin>>a[i],V=max(V,a[i]);
    for(int i=1;i<=m;++i)
    	cin>>b[i],V=max(V,b[i]);
    sort(a+1,a+n+1);
     sort(b+1,b+m+1);
     m=unique(b+1,b+m+1)-b-1;
    memset(dp,inf,sizeof(dp)),dp[1]=0;
    for(int i=1;i<=m;++i)
    	for(int s=b[i];s<=V;s+=b[i])
    		dp[s]=min(dp[s],dp[s/b[i]]+1);
	for(int i=1;i<=a[1]/i;++i)
		if(a[1]%i==0)
			ans=min({ans,get(i),get(a[1]/i)});
	if(ans==inf)
		ans=-1;
	cout<<ans<<endl;
	return 0;
}