【BZOJ4916】神犇和蒟蒻（杜教筛）

题面

\[\sum_{i=1}^n\mu(i^2)\ \ 和\ \sum_{i=1}^n\varphi(i^2)
\]

其中$$n<=10^9$$

题解

第一问

搞笑的

不会做？

算了。。

还是说一下：

想想$\mu(x)$是怎么算的？？？

既然是$i^2$，每个因数的个数一定不会是$1$

所以除了$\mu(1)$外一定都是$0$

所以第一问的答案一定是$1$

第二问：

先看看要求的是什么

$\varphi(i^2)=i*\varphi(i)$

为啥？？？

想想你线性筛是怎么写的，那么这个东西就很明显了。

$10^9$的范围

看着就不能线性筛

于是想到了杜教筛

设$f(i)=\varphi(i^2)=i\varphi(i)$

$S(n)=\sum_{i=1}^nf(i)$

现在先搞一个$g(x)$出来，可以推出式子

（难道这就是杜教筛的套路式子吗？？）

\[g(1)S(n)=\sum_{i=1}^n(f*g)(i)-\sum_{i=2}^ng(i)S(\frac{n}{i})
\]

现在要做的就是构造一个$g(x)$使得前面那玩意很好算

看一看$f(i)=i\varphi(i)$

往$\varphi(i)$的性质上面靠：

$\sum_{d|i}\varphi(d)=i$

要让$$(f*g)(i)=\sum_{d|i}f(d)g(\frac{i}{d})$$好算前缀和

直接写一下：

\[(f*g)(i)=\sum_{d|i}\varphi(d)dg(\frac{i}{d})
\]

要是能够把$d$给搞掉多好，所以$g(\frac{i}{d})$最好能够把$d$搞掉

发现令$g(x)=x$就可以啦

\[(f*g)(i)=\sum_{d|i}\varphi(d)d\frac{i}{d}
\]

\[=\sum_{d|i}\varphi(d)i
\]

\[=i\sum_{d|i}\varphi(d)
\]

\[=i^2
\]

这个玩意的前缀和多好算

\[\sum_{i=1}^n(g*f)(i)=1^2+2^2+.....n^2=\frac{n(n+1)(2n+1)}{6}
\]

所以把那个我认为的杜教筛的套路式子拿出来

\[g(1)S(n)=\sum_{i=1}^n(f*g)(i)-\sum_{i=2}^ng(i)S(\frac{n}{i})
\]

\[S(n)=\frac{n(n+1)(2n+1)}{6}-\sum_{i=2}^niS(\frac{n}{i})
\]

看起来可以杜教筛了嗷。。。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define MAX 10000000

#define MOD 1000000007

int n,N;

int pri[MAX+10],phi[MAX+10],tot,inv=166666668;

bool zs[MAX+10];

map<int,int> M;

void pre(int N)

{

	zs[1]=true;phi[1]=1;

	for(int i=2;i<=N;++i)

	{

		if(!zs[i])pri[++tot]=i,phi[i]=i-1;

		for(int j=1;j<=tot&&i*pri[j]<=N;++j)

		{

			zs[i*pri[j]]=true;

			if(i%pri[j])phi[i*pri[j]]=1ll*phi[i]*phi[pri[j]]%MOD;

			else{phi[i*pri[j]]=1ll*phi[i]*pri[j]%MOD;break;}

		}

	}

	for(int i=1;i<=N;++i)phi[i]=(1ll*i*phi[i]%MOD+phi[i-1])%MOD;

}

int S(int x)

{

	if(x<=N)return phi[x];

	if(M[x])return M[x];

	int ret=1ll*x*(x+1)%MOD*(x+x+1)%MOD*inv%MOD;

	for(int i=2,j;i<=x;i=j+1)

	{

		j=x/(x/i);

		int tt=1ll*(i+j)*(j-i+1)/2%MOD;

		ret-=1ll*tt*S(x/i)%MOD;

		ret%=MOD;

	}

	return M[x]=(ret+MOD)%MOD;

}

int main()

{

	scanf("%d",&n);puts("1");

	pre(N=min(n,MAX));

	printf("%d\n",S(n));

	return 0;

}

巴特西

【BZOJ4916】神犇和蒟蒻（杜教筛）

【BZOJ4916】神犇和蒟蒻（杜教筛）

题面

题解

最新文章

热门文章