【2019.8.11下午 慈溪模拟赛 T2】数数(gcd)(分块+枚举因数)

【2019.8.11下午 慈溪模拟赛 T2】数数(gcd)(分块+枚举因数)
强烈推介IDEA2021.1.3破解激活,IntelliJ IDEA 注册码,2021.1.3IDEA 激活码 

大家好,我是架构君,一个会写代码吟诗的架构师。今天说一说【2019.8.11下午 慈溪模拟赛 T2】数数(gcd)(分块+枚举因数),希望能够帮助大家进步!!!

莫比乌斯反演

考虑先推式子:

\[\sum_{i=l}^r[gcd(a_i,G)=1]\]

\[\sum_{i=l}^r\sum_{p|a_i,p|G}\mu(p)\]

\[\sum_{p|G}\mu(p)\sum_{i=l}^r[p|a_i]\]

因此我们只要枚举询问的这个数的因数,然后求出这段区间内有多少个数是它的倍数即可。

分块

我们可以统计对于每个数,每个块内有多少个数是其倍数。

数的规模\(O(n)\),块大小\(O(\sqrt n)\),所以内存是\(O(n\sqrt n)\),询问是\(O(\sqrt n)\),修改是\(O(1)\)

但由于询问和修改都需要枚举因数,因此时间复杂度还要乘上一个数的不含平方因子的因数个数,这个最大是\(60\)左右。

因此复杂度是\(O(60n\sqrt n)\)

代码

#pragma GCC optimize(2) #include<bits/stdc++.h> #define Tp template<typename Ty> #define Ts template<typename Ty,typename... Ar> #define Reg register #define RI Reg int #define Con const #define CI Con int& #define I inline #define W while #define N 50000 #define V 100000 using namespace std; int n,a[N+5]; class FastIO { private: #define FS 100000 #define tc() (A==B&&(B=(A=FI)+fread(FI,1,FS,stdin),A==B)?EOF:*A++) #define pc(c) (C==E&&(clear(),0),*C++=c) #define tn (x<<3)+(x<<1) #define D isdigit(c=tc()) int T;char c,*A,*B,*C,*E,FI[FS],FO[FS],S[FS]; public: I FastIO() {A=B=FI,C=FO,E=FO+FS;} Tp I void read(Ty& x) {x=0;W(!D);W(x=tn+(c&15),D);} Tp I void write(Ty x) {W(S[++T]=x%10+48,x/=10);W(T) pc(S[T--]);} Tp I void writeln(Con Ty& x) {write(x),pc('\n');} I void clear() {fwrite(FO,1,C-FO,stdout),C=FO;} }F; class BlockSolver//分块 { private: template<int SZ> class LinearSiever//线性筛 { private: int Pt,P[SZ+5]; public: int mu[SZ+5]; I LinearSiever() { mu[1]=1;for(RI i=2,j;i<=SZ;++i) for(!P[i]&&(mu[P[++Pt]=i]=-1),j=1;1LL*i*P[j]<=SZ;++j) if(P[i*P[j]]=1,i%P[j]) mu[i*P[j]]=-mu[i];else break; } };LinearSiever<V> L; template<int SZ,int BT,int BS> class Block//分块 { private: int bl[SZ+5],s[BT+5][SZ+5]; public: I Block() {for(RI i=1;i<=SZ;++i) bl[i]=(i-1)/BS+1;}//初始化 I void Upt(CI p,CI x,CI y) {s[bl[p]][x]+=y;}//单点修改 I int Qry(CI l,CI r,CI k)//区间询问 { #define BF(x,y) for(RI i=x,t=y;i<=t;++i) res+=!(a[i]%k); RI res=0;if(bl[l]==bl[r]) {BF(l,r);return res;} BF(l,bl[l]*BS);BF((bl[r]-1)*BS+1,r); for(RI i=bl[l]+1;i^bl[r];++i) res+=s[i][k];return res; } };Block<V,500,300> B; int sz[V+5],v[V+5][80]; public: I void Solve() { RI Qt,i,j,op,x,y,z,t;for(i=1;i<=V;++i) for(j=1;j*j<=i;++j) !(i%j)&&(L.mu[j]&&(v[i][++sz[i]]=j),(j*j)^i&&L.mu[i/j]&&(v[i][++sz[i]]=i/j));//预处理每个数不含平方因子的因数 for(i=1;i<=n;++i) for(j=1;j<=sz[a[i]];++j) B.Upt(i,v[a[i]][j],1);//预处理 F.read(Qt);W(Qt--) { if(F.read(op),F.read(x),F.read(y),op==1)//修改 { for(i=1;i<=sz[a[x]];++i) B.Upt(x,v[a[x]][i],-1);a[x]=y;//删去原贡献 for(i=1;i<=sz[a[x]];++i) B.Upt(x,v[a[x]][i],1);//更新新贡献 } else { for(F.read(z),t=0,i=1;i<=sz[z];++i) t+=L.mu[v[z][i]]*B.Qry(x,y,v[z][i]);//枚举因数统计答案 F.writeln(t);//输出答案 } } } }S; int main() { freopen("gcd.in","r",stdin),freopen("gcd.out","w",stdout); RI i;for(F.read(n),i=1;i<=n;++i) F.read(a[i]);return S.Solve(),F.clear(),0; }

转载于:https://www.cnblogs.com/chenxiaoran666/p/Contest20190811afternoonT2.html

本文来源weixin_30595035,由架构君转载发布,观点不代表Java架构师必看的立场,转载请标明来源出处:https://javajgs.com/archives/29490

发表评论