题目传送门
题目分析
简化题意
对每个数进行质因数分解，如果质因数在题目中给出为坏质数答案就 $-1$，不然答案就 $+1$ 算所有数计算出的答案的总和的最小值。
做法
我们求出每个数的前缀 $\gcd$ 然后预处理出 $10^6$ 以内的质数，后处理的时候从后向前枚举，判断当前数的前缀 $\gcd$ 进行题目中的计算得到的数是正数还是负数，如果是正数就保留，不然就全部除以这个数这里利用一个 $used$ 记录要除以的数，类似线段树中的懒标记，处理每个数就按照质因数分解，利用预处理出的质数集去遍历，判断能否被整除，时间复杂度是线性的。
code
#include<bits/stdc++.h>
#define int long long
const int N=5005;
const int M=1000006;
using namespace std;
inline int read(){
int t=1,x=0;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') t=-1;
for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
return t*x;
}//快读
int n,m;
int a[N],num[N];
int pre[M],pr;
bool pd[M];
unordered_map<int,int> be;//要用map不然数字会超过范围，会RE
int ans;
int gcd[N];//前缀数组
void init(){
int x=1e6;
for(int i=2;i<=x;i++){
if(!pd[i]) pre[++pr]=i;
for(int j=1;pre[j]*i<=x&&j<=pr;j++){
pd[pre[j]*i]=1;
if(i%pre[j]==0) break;
}
}
}//预处理出所有的质数
int dfs(int x){
int res=0;
for(int i=1;pre[i]*pre[i]<=x;i++){
int cnt=0;
while(x%pre[i]==0) x/=pre[i],cnt++;
res+=cnt*(be[pre[i]]?-1:1);
if (x==1) break;
}
if(x>1) res+=(be[x]?-1:1);
return res;
}//每个数的质因数分解
signed main(){
init();
n=read(),m=read();
for(int i=1;i<=n;i++){
a[i]=read();
}
gcd[1]=a[1];//对于第一个数的前缀数组要进行特判
for(int i=2;i<=n;i++){
gcd[i]=__gcd(gcd[i-1],a[i]);//__gcd是内置函数，比较好用
}
for(int i=1;i<=m;i++){
num[i]=read();
be[num[i]]=1;//给b数组的每一个数打上标记
}
for(int i=1;i<=n;i++)ans+=dfs(a[i]);
int used=1;//used用来记录上一个要除去的数
for(int i=n;i;i--) {
if(gcd[i]/used==1)continue;//特判，小优化，也可以去掉
int p=dfs(gcd[i]/used);
if(p<0){
ans-=p*i;
used=gcd[i];
}
}
cout<<ans;
return 0;
}
后记
$long long$ 要看准时机开，不要开可以不开。