杜教筛

[BZOJ3944]Sum

Posted by Dispwnl on August 29, 2018

题目

Description

Input

一共T+1行

第1行为数据组数T(T<=10)

第2~T+1行每行一个非负整数N，代表一组询问

Output

一共T行，每行两个用空格分隔的数ans1,ans2

Sample Input

6
1
2
8
13
30
2333

Sample Output

1 1
2 0
22 -2
58 -3
278 -3
1655470 2

题解

最该死的就是这种贴图题了，而最最该死的就是这种要卡常的贴图题了

题目要求：$\sum_{i=1}^{n}\phi(i),\sum_{i=1}{n}\mu(i)$

如果$n$的范围小一点就可以用线筛直接搞

但这题直接搞是自己找TLE

要用到一个叫杜教筛的东西

先看$\mu$，设$S(n)=\sum_{i=1}^{n}\mu(i)$

找个积性函数（随便找一个）$f$与$\mu$做狄利克雷卷积，得到：$(f*\mu)(i)$

即：$\sum_{d\vert i}\mu(d)f(\frac{i}{d})$

求前缀和：$\sum_{i=1}^{n}\sum_{d\vert i}\mu(d)f(\frac{i}{d})$

式子可以化为：$\sum_{d=1}^{n}f(d)\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\mu(i)$

后面部分就是设的$S$了：$\sum_{d=1}^{n}f(d)S(\left\lfloor\frac{n}{d}\right\rfloor)$

有$f(1)S(n)=\sum_{d=1}^{n}f(d)S(\left\lfloor\frac{n}{d}\right\rfloor)-\sum_{d=2}^{n}f(d)S(\left\lfloor\frac{n}{d}\right\rfloor)$

前面是个卷积的形式，$d$从1开始枚举的，所以可以化成：$\sum_{d=1}^{n}(f*\mu)(d)-\sum_{d=2}^{n}f(d)S(\left\lfloor\frac{n}{d}\right\rfloor)$

$\mu$函数有一个性质：$\sum_{i\vert n}\mu(i)=[n==1]$

当$f(x)=1$时，有：$\sum_{d=1}^{n}(f*\mu)(d)=\sum_{d=1}^{n}\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\mu(i)=\sum_{d=1}^{n}\sum_{d\vert x}\mu(d)=1$

所以答案$S(n)=1-\sum_{d=2}^{n}S(\left\lfloor\frac{n}{d}\right\rfloor)$

前面可以先线筛$n^{\frac{2}{3}}$的数据，后面部分可以用个递归来求

再来看下$\phi$

$\phi$也有一个类似的性质：$\sum_{i\vert n}\phi(i)=i$

剩下的都一样，当$f(x)=1$时，有：$\sum_{d=1}^{n}(f*\phi)(d)=\sum_{d=1}^{n}\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\phi(i)=\sum_{d=1}^{n}\sum_{d\vert x}\mu(d)=\frac{n(n+1)}{2}$

所以答案$S(n)=\frac{n(n+1)}{2}-\sum_{d=2}^{n}S(\left\lfloor\frac{n}{d}\right\rfloor)$，也可以递归求解

开始用$map$存大数，然后T的很惨QAQ

代码

# include<iostream>
# include<cstring>
# include<cstdio>
# include<map>
# include<algorithm>
# define LL long long
using namespace std;
const int MAX=2e6+1;
int t,tot;
LL n;
int pm[MAX];
LL u[MAX],phi[MAX],mu[MAX],ph[MAX];
bool use[MAX],vis[MAX];
void dfs(LL x)
{
	if(x<MAX) return;
	int tt=n/x;
	if(vis[tt]) return;
	vis[tt]=1,mu[tt]=1,ph[tt]=x*(x+1)/2;
	for(LL l=2,r;l<=x;l=r+1)
	  r=x/(x/l),dfs(x/l),mu[tt]-=1ll*(r-l+1)*(x/l<MAX?u[x/l]:mu[n/(x/l)]),ph[tt]-=1ll*(r-l+1)*(x/l<MAX?phi[x/l]:ph[n/(x/l)]);
}
int main()
{
	u[1]=phi[1]=1;
	for(int i=2;i<MAX;++i)
	  {
	  	if(!use[i]) pm[++tot]=i,u[i]=-1,phi[i]=i-1;
	  	for(int j=1;j<=tot&&i*pm[j]<MAX;++j)
	  	  {
	  	  	use[i*pm[j]]=1;
	  	  	if(i%pm[j]==0)
	  	  	{
	  	  		u[i*pm[j]]=0,phi[i*pm[j]]=phi[i]*pm[j];
	  	  		break;
			}
			u[i*pm[j]]=-u[i],phi[i*pm[j]]=phi[i]*phi[pm[j]];
		  }
	  }
	for(int i=1;i<MAX;++i)
	  u[i]+=u[i-1],phi[i]+=phi[i-1];
	scanf("%d",&t);
	while(t--)
	{
		scanf("%lld",&n);
		if(n<MAX)
		{
			printf("%lld %lld\n",phi[n],u[n]);
			continue;
		}
		memset(vis,0,sizeof(vis));
		dfs(n);
		printf("%lld %lld\n",ph[1],mu[1]);
	}
	return 0;
}
MUSIC
    FRIENDS