若数学公式无法显现请自行刷新




此题最大的坑点在数据范围，他不写到方框里面我还以为a[i],b[i]都在1e6，给我考场上爆成30分了

一道好题

首先我们观察f(s)的生成方式，容易看出这与线性筛的筛法有很多相似之处。再注意到输入中输入有许多坏素数，就容易想到线性筛了。

我们可以轻易地预处理出1e6范围内的素数，顺便处理出他们的f值

const int M = 1e6+10;

int not_prime[M],prime[M],f[M],pcnt=0;
void init_prime(){
    for(re int i=2;i<=(M-9);++i){
        if(!not_prime[i])    prime[++pcnt]=i,f[i]=isbad_prime[i]?-1:1;
        for(re int j=1;j<=pcnt&&prime[j]*i<=(M-9);++j){
            not_prime[prime[j]*i]=1,f[prime[j]*i]=f[i]+(isbad_prime[prime[j]]?-1:1);
            if(!i%prime[j])    break;
        }
    }
}

推出 $a[i]>1e6$ 时 $f[a[i]]$ 的计算方式其实也是顺理成章

ll calc(ll x){
    if(isbad_prime[x])    return -1;
    if(x<M-9)    return f[x];
    for(int i=1;i<=pcnt&&prime[i]<=x;++i)
        if(x%prime[i]==0)
            return calc(x/prime[i])+(isbad_prime[prime[i]]?-1:1);
    return 1;
}

至于最终的前缀GCD修改，其实只是看着唬人。考场上我看到带修改就先跳了这道，结果最后发现这道最简单。（然而仍然没有1A）考虑到由坏素数筛出的数中间一定有$f[t]=f[k]-1$这步过程，要$\sum_{i=1}^Nf[i]$最大，自然希望把GCD中的坏素数都修改掉。

我们就能得出贪心：

从后往前枚举前缀的公共gcd $g[i]$ ,当 $f[g[i]]<0$ 时，说明这个时候坏素数应该被筛掉了。这样依次进行……

数学证明等我有空再写

AC代码（又长又慢）:

#include <bits/stdc++.h>
#define re register
using namespace std;
typedef long long ll;

inline int red(){
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}

const int N = 2010;
const int K = 1e9+5;
const int M = 1e5+10;

int n,m;
int a[N],f[M];
int bad_prime[N],bcnt=0;
bitset <K> isbad_prime;
int not_prime[M],prime[M],pcnt=0;
void init_prime(){
    for(re int i=2;i<=(M-9);++i){
        if(!not_prime[i])    prime[++pcnt]=i,f[i]=isbad_prime[i]?-1:1;
        for(re int j=1;j<=pcnt&&prime[j]*i<=(M-9);++j){
            not_prime[prime[j]*i]=1,f[prime[j]*i]=f[i]+(isbad_prime[prime[j]]?-1:1);
            if(!i%prime[j])    break;
        }
    }
}

ll g[N];
ll gcd(int a,int b){return b?gcd(b,a%b):a;}
void init_gcd(){
    for(re int i=1;i<=n;++i)    g[i]=gcd(a[i],g[i-1]);
}

ll calc(ll x){
    if(isbad_prime[x])    return -1;
    if(x<M-9)    return f[x];
    for(int i=1;i<=pcnt&&prime[i]<=x;++i)
        if(x%prime[i]==0)
            return calc(x/prime[i])+(isbad_prime[prime[i]]?-1:1);
    return 1;
}

int main(){
    n=red(),m=red();
    for(re int i=1;i<=n;++i)    a[i]=red();
    for(re int i=1;i<=m;++i)    bad_prime[++bcnt]=red(),isbad_prime[bad_prime[bcnt]]=1;
    init_prime();
    init_gcd();
    ll ans=0,tag=1;
    for(re int i=1;i<=n;++i)    ans+=calc(a[i]);
    for(re int i=n;i;--i){
        g[i]/=tag;
        ll tmp=calc(g[i]);
        if(tmp<0)    ans-=tmp*1LL*i,tag*=g[i];
    }
    printf("%lld",ans);
    return 0;
}