CF402D 题解

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