分析

注意到 \(f\) 的过程就是唯一分解的过程。

考虑 \(g = \gcd\{a_{1 \sim i}\}\)，发现除去 \(g\) 之后，相当于原来的总和减去 \(f(g)\)，贡献为 \(i \times -f(g)\)。

设 \(F(i)\) 为以 \(i\) 结尾的前缀，能够产生的最大贡献。

由于可以进行多次，所以可能在让 \(a_{1 \sim i}\) 除去 \(g\) 之前，其中某些数已经被修改过了，所以枚举 \(j \in [1,i-1]\)，表示前缀 \([1,j]\) 中已经没有了 \(g\) 这个因子，因此 \[ F(i) = \min_{j \in [0,i-1]} \{ F(j) + (i-j) \times - f(g) \} \] 通过操作产生的最大贡献为 \(F_{\max}\)。

CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
const int N=1e5+5;
int n, m, dlt, ans, a[N], f[N];
int cnt, v[N], p[N];
unordered_map<int,bool> bad;
int gcd(int x,int y) { return y? gcd(y,x%y):x; }
void ora() {
	for(int i=2;i<=1e5;++i) {
		if(!v[i]) p[++cnt]=i;
		for(int j=1;j<=cnt&&i*p[j]<=1e5;++j) {
			v[i*p[j]]=1;
			if(i%p[j]==0) break;
		}
	}
}
int F(int x) {
	int d=0;
	for(int i=1;p[i]*p[i]<=x;++i) if(x%p[i]==0) {
		int tot=0;
		while(x%p[i]==0) x/=p[i], ++tot;
		d+=bad[p[i]]? -tot:tot;		
	}
	if(x!=1) d+=bad[x]? -1:1;
	return d;
}
signed main() {
	ora();
	n=read(), m=read();
	for(int i=1;i<=n;++i) a[i]=read();
	for(int i=1;i<=m;++i) bad[read()]=1;
	for(int i=1;i<=n;++i) dlt+=F(a[i]);
	int g=0;
	for(int i=1;i<=n;++i) {
		g=gcd(g,a[i]);
		int d=F(g);
		f[i]=i*(-d);
		for(int j=1;j<i;++j) f[i]=max(f[i],f[j]+(i-j)*(-d));
		ans=max(ans,f[i]);
	}
	printf("%lld\n",dlt+ans);
}