P9589 「PFLOI R1」PFL 除法

题目背景

有必要把所有比赛题的背景连在一起。

就这样，新世界的大门向它们敞开了……

“喵！”一只可爱的花猫向它们问好。

“你们刚来到这？”

“嗯。”

“我带你们去转转吧，谁叫我这么可爱呢！”

“……” 花猫突然止住，打量一番手中的序列，俶尔又微笑着说：

“但你们要先答出我的问题哦。”

题目描述

花猫有一个长度为 $n$ 的序列 $A$ 和另一个长度为 $m$ 的序列 $B$。你可以进行若干次以下操作：

• 选择两个整数 $i$ 和 $j$，满足 $1\le i\le n$，$1\le j\le m$ 且 $B_j\mid A_i$，然后将 $A_i$ 变为 $\frac{A_i}{B_j}$。

注意：$A$ 和 $B$ 中的每个元素都可以选择并被操作多次。

最终要使得 $A$ 中的元素都相等，请求出最少的操作次数；若无解，输出 -1。

输入格式

第一行两个正整数 $n$ 和 $m$。

第二行 $n$ 个正整数表示序列 $A$。

第三行 $m$ 个正整数表示序列 $B$。

输出格式

输出一个整数表示最少的操作次数；若无解，输出 -1。

输入输出样例 #1

输入 #1

4 5
16 24 28 36
11 4 7 3 2

输出 #1

6

输入输出样例 #2

输入 #2

2 3
11 13
13 1 11

输出 #2

2

输入输出样例 #3

输入 #3

2 2
2 3
4 5

输出 #3

-1

说明/提示

本题采用捆绑测试。

子任务编号	特殊性质	分值
$1$	$A$ 中所有元素相等	$5$
$2$	$n=2$	$15$
$3$	$n,m\le 10^3$	$20$
$4$	$n,m\le 10^4$	$20$
$5$	无	$40$

对于所有数据，$1\le n,m\le 5\times 10^5$，$1\le A_i,B_i\le 5\times 10^5$。

C++实现

#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;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容