【CCPC-Wannafly Winter Camp Day3 (Div1) F】小清新数论（莫比乌斯反演+杜教筛）

点此看题面

大致题意： 让你求出\(\sum_{i=1}^n\sum_{j=1}^n\mu(gcd(i,j))\)。

莫比乌斯反演

这种题目，一看就是莫比乌斯反演啊！（连莫比乌斯函数都有）

关于莫比乌斯反演，详见这篇博客：初学莫比乌斯反演。

推式子

下面让我们来推式子。

首先，我们采用解决这种问题的常用套路，来枚举\(gcd\)，就能得到这样一个式子：

\[\sum_{d=1}^n\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac nd\rfloor}[gcd(i,j)==1]\mu(d)
\]

将\(\mu(d)\)提前，可得：

\[\sum_{d=1}^n\mu(d)\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac nd\rfloor}[gcd(i,j)==1]
\]

针对后半部分的式子，考虑当\(i>j\)时，其实等价于\(i\)和\(j\)交换后的答案。

这样一来，我们就可以想到把\(j\)的上限改为\(i\)。

注意\(i=j\)时，若\(i=j=1\)，则\(gcd(i,j)=1\)，其余情况\(gcd(i,j)\)必定不为\(1\)，因此要单独处理这种情况，将结果减\(1\)。

于是就得到这样一个式子：

\[\sum_{d=1}^n\mu(d)(2\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^i[gcd(i,j)==1]-1)
\]

根据\(\phi\)的定义可得，\(\sum_{j=1}^i[gcd(i,j)==1]\)其实就等于\(\phi(i)\)，因此可得：

\[\sum_{d=1}^n\mu(d)(2\sum_{i=1}^{\lfloor\frac nd\rfloor}\phi(i)-1)
\]

这时的式子就已经足够简单了。

求答案

考虑如何求答案。

由于值域较大，因此我们必须使用杜教筛来筛\(\mu\)和\(\phi\)这两个函数。

由于后半部分的上限\(\lfloor\frac nd\rfloor\)，因此我们必须使用除法分块来对这个式子进行优化。

这样就可以了。

代码

#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 X 998244353

#define LL long long

#define Inc(x,y) ((x+=(y))>=X&&(x-=X))

#define Dec(x,y) ((x-=(y))<0&&(x+=X))

#define XSum(x,y) ((x)+(y)>=X?(x)+(y)-X:(x)+(y))

using namespace std;

LL n;

class DuSiever//杜教筛

{

	private:

		static const int SZ=10000000;int Pcnt,P[SZ+5],phi[SZ+5],mu[SZ+5],Sphi[SZ+5],Smu[SZ+5];

		map<LL,int> Mphi,Mmu;

	public:

		I DuSiever()//初始化

		{

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

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

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

			for(i=1;i<=SZ;++i) Sphi[i]=XSum(Sphi[i-1],phi[i]),Smu[i]=XSum(XSum(Smu[i-1],mu[i]),X);

		}

		I int Gphi(Con LL& x)//筛phi

		{

			if(x<=SZ) return Sphi[x];if(Mphi.count(x)) return Mphi[x];

			RI res=1LL*x%X*(x+1)%X*(X+1>>1)%X;Reg LL l,r;//千万注意此处x直接乘x+1会爆long long，因此要先取模（为此调了一个小时）

			for(l=2;l<=x;l=r+1) r=x/(x/l),Dec(res,1LL*(r-l+1)*Gphi(x/l)%X);

			return Mphi[x]=res;

		}

		I int Gmu(Con LL& x)//筛mu

		{

			if(x<=SZ) return Smu[x];if(Mmu.count(x)) return Mmu[x];

			RI res=1;Reg LL l,r;

			for(l=2;l<=x;l=r+1) r=x/(x/l),Dec(res,1LL*(r-l+1)*Gmu(x/l)%X);

			return Mmu[x]=res;

		}

}D;

int main()

{

	RI ans=0;Reg LL l,r;for(scanf("%lld",&n),l=1;l<=n;l=r+1)//除法分块

		r=n/(n/l),Inc(ans,1LL*(D.Gmu(r)-D.Gmu(l-1)+X)%X*((D.Gphi(n/l)<<1)-1)%X);

	return printf("%d",ans),0;//输出答案

}

巴特西

【CCPC-Wannafly Winter Camp Day3 (Div1) F】小清新数论（莫比乌斯反演+杜教筛）

莫比乌斯反演

推式子

求答案

代码

最新文章

热门文章