【51nod1678】lyk与gcd（莫比乌斯反演+枚举因数）

点此看题面

大致题意： 一个长度为\(n\)的数组，实现两种操作：单点修改，给定\(i\)求\(\sum_{j=1}^na_j[gcd(i,j)=1]\)。

莫比乌斯反演

考虑推一推询问操作的式子：

\[\sum_{j=1}^na_j[gcd(i,j)=1]
\]

按照莫比乌斯反演的一般套路，我们知道\(\sum_{p|x}\mu(p)=[x=1]\)，因此我们枚举一个\(p\)：

\[\sum_{j=1}^na_j\sum_{p|i,p|j}\mu(p)
\]

调整枚举顺序，得到：

\[\sum_{p|i}\mu(p)\sum_{j=1}^na_j[p|j]
\]

考虑到一个数的约数个数很少，所以我们可以直接枚举\(p\)，然后只要维护满足\(p|j\)的\(a_j\)之和，就可以求出答案。

则我们可以发现，同样因为一个数的约数个数很少，单点修改时，我们可以枚举所修改位置的编号的约数并修改每个约数的答案，这样就能实现维护了。

代码

#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 100000

#define IT vector<int>::iterator

#define pb push_back

using namespace std;

int n,a[N+5],s[N+5];vector<int> v[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 LinearSieve//线性筛预处理莫比乌斯函数

{

	private:

		int Pt,P[N+5],mu[N+5];

	public:

		I int operator [] (CI x) Con {return mu[x];}

		I LinearSieve()

		{

			mu[1]=1;for(RI i=2,j;i<=N;++i)

				for(!P[i]&&(mu[P[++Pt]=i]=-1),j=1;j<=Pt&&1LL*i*P[j]<=N;++j)

					if(P[i*P[j]]=1,i%P[j]) mu[i*P[j]]=-mu[i];else break;

		}

}L;

int main()

{

	RI Qt,i,j,op,x,y,t;IT it;for(F.read(n),F.read(Qt),i=1;i<=n;++i)

	{

		for(F.read(a[i]),j=1;1LL*j*j<=i;++j) !(i%j)&&(v[i].pb(j),i^(j*j)&&(v[i].pb(i/j),0));//预处理约数

		for(it=v[i].begin();it!=v[i].end();++it) s[*it]+=a[i];//预处理答案

	}

	W(Qt--) switch(F.read(op),F.read(x),op)

	{

		case 1:for(F.read(y),it=v[x].begin();it!=v[x].end();++it) s[*it]+=y-a[x];a[x]=y;break;//单点修改，枚举约数进行修改

		case 2:for(t=0,it=v[x].begin();it!=v[x].end();++it) t+=L[*it]*s[*it];F.writeln(t);break;//询问，枚举约数统计答案

	}return F.clear(),0;

}

巴特西

【51nod1678】lyk与gcd（莫比乌斯反演+枚举因数）

莫比乌斯反演

代码

最新文章

热门文章