BZOJ3944 Sum 数论 杜教筛

原文链接http://www.cnblogs.com/zhouzhendong/p/8671759.html

题目传送门 - BZOJ3944

题意

　　多组数据（组数<=10)。

　　每组数据一个正整数$n(n\leq 10^{10})$。

　　让你求$\sum_{i=1}^{n}\varphi(i)$以及$\sum_{i=1}^{n}\mu(i)$。

题解

　　杜教筛模版题。

　　杜教筛学习->传送门

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=2e6+5;

int lim=2e6,T;

LL n,prime[N],pcnt,u[N],phi[N],U[N],Phi[N];

int vis[N],mark=0;

void init(int n){

	memset(phi,0,sizeof phi);

	u[1]=phi[1]=1;

	for (int i=2;i<=n;i++){

		if (!phi[i])

			prime[++pcnt]=i,u[i]=-1,phi[i]=i-1;

		for (int j=1;j<=pcnt&&prime[j]*i<=n;j++){

			int k=prime[j]*i;

			if (i%prime[j])

				u[k]=-u[i],phi[k]=phi[i]*(prime[j]-1);

			else {

				u[k]=0,phi[k]=phi[i]*prime[j];

				break;

			}

		}

	}

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

		u[i]+=u[i-1],phi[i]+=phi[i-1];

	memset(vis,0,sizeof vis);

}

void solve(LL x){

	if (x<=lim)

		return;

	LL y=n/x;

	if (vis[y]==mark)

		return;

	vis[y]=mark;

	U[y]=1,Phi[y]=x*(x+1)/2;

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

		j=x/(x/i);

		solve(x/i);

		U  [y]-=(x/i<=lim?u  [x/i]:U  [n/(x/i)])*(j-i+1);

		Phi[y]-=(x/i<=lim?phi[x/i]:Phi[n/(x/i)])*(j-i+1);

	}

}

int main(){

	init(lim);

	scanf("%d",&T);

	while (T--){

		scanf("%lld",&n);

		if (n<=lim)

			printf("%lld %lld\n",phi[n],u[n]);

		else {

			mark++;

			solve(n);

			printf("%lld %lld\n",Phi[1],U[1]);

		}

	}

	return 0;

}