2023-09-04 18:42:46 solution
不难想到我们要先记录一下每一位的前缀 \(\gcd\)，我们发现我们选择一位的前缀 \(\gcd\) 除掉以后，前缀 \(\gcd\) 会变为 \(1\) 并且会导致这位之后的 \(\gcd\) 全部为 \(1\)。所以每一位只能选择一次，并且我们从后往前扫肯定比从前往后扫要更优。
我们先把原序列原答案算出来，然后判断每一次除当前位的 \(\gcd\) 是否对答案有正贡献，贪心选择。这样为什么对呢？考虑我们第 \(i\) 位的贡献为正，但是我们不选，到 \(i-1\) 的时候，贡献可能变大，那显然我们后面除了对前面也没有影响，前面依然可以除剩下的，但是如果变小，说明前面不用除要让后面除。所以我们贪心从后往前选择是更优的。
如果我们直接贪心选了以后把前面的 \(\gcd\) 都除掉，发现复杂度是 \(O(n^2\sqrt{a})\) 的，这样肯定不行。注意到我们 \(\gcd\) 是单调不增的，所以我们从后往前是单调不减的，记录一下即可做到 \(O(n\sqrt{a})\)，然而用线性筛跑了之后是远远跑不满的。
\(Code\)
int n,m,tot,prime[100005];
bool vis[100005];
ll ans,a[5002],b[5002];
unordered_set<ll>pd;
void init(){
for(int i=2;i<=100000;i++){
if(!vis[i])prime[++tot]=i;
for(int j=1;j<=tot&&prime[j]*i<=100000;j++){
vis[prime[j]*i]=1;
if(i%prime[j]==0)break;
}
}
}
ll cal(ll x){
ll res=0;
for(int i=1;prime[i]*prime[i]<=x;i++){
if(x%prime[i])continue;
ll cnt=0;
while(x%prime[i]==0)x/=prime[i],cnt++;
if(pd.find(prime[i])!=pd.end())res-=cnt;
else res+=cnt;
}
if(x>1){
if(pd.find(x)!=pd.end())res--;
else res++;
}
return res;
}
int main(){
n=read(),m=read();
init();
for(int i=1;i<=n;i++){
a[i]=read();
if(i==1)b[i]=a[i];
else b[i]=__gcd(b[i-1],a[i]);
}
for(int i=1;i<=m;i++)pd.insert(read());
for(int i=1;i<=n;i++)ans+=cal(a[i]);
for(ll i=n,used=1,o;i;--i)
if((b[i]/used>1)&&(o=cal(b[i]/used))<0)ans-=o*i,used=b[i];
cout<<ans;
return 0;
}