洛阳杯[数论][线性筛]

本文主要是介绍洛阳杯[数论][线性筛]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 

---

分析

(https://blog.csdn.net/forever_dreams/article/details/83450135)

---

#include<bits/stdc++.h>
#define N 100005
using namespace std;
int n,m,a[N],isp[N],prim[N],tot;
int g[N],ans;
bitset<1000000000> S;
int read(){int cnt=0; char ch=0;while(!isdigit(ch)) ch=getchar();while(isdigit(ch))cnt=cnt*10+(ch-'0'),ch=getchar();return cnt;
}
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
void init(){for(int i=2;i<=N-5;i++){if(!isp[i]) isp[i]=1,prim[++tot]=i;for(int j=1;j<=tot && prim[j]*i<=N-5;j++){isp[i*prim[j]]=1;if(i%prim[j]==0) break;}} 
}
int divide(int x){int ans=0;for(int i=1;i<=tot && prim[i]*prim[i]<=x;i++){while(x%prim[i]==0) ans+=S[prim[i]]?-1:1,x/=prim[i];}if(x>1) ans+=S[x]?-1:1;return ans;
}
int main(){n=read(),m=read();for(int i=1;i<=n;i++) a[i]=read();for(int i=1;i<=m;i++) S[read()]=1;init();for(int i=1;i<=n;i++) ans+=divide(a[i]);for(int i=1;i<=n;i++) g[i]=gcd(g[i-1],a[i]);int div=1;for(int i=n;i>=1;i--){g[i]/=div;int x=divide(g[i]);if(x<0) ans+=i*(-x),div*=x;}printf("%d\n",ans);return 0;
}

 

这篇关于洛阳杯[数论][线性筛]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---