题面

Description

Input

一共T+1行

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

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

Output

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

Sample Input

2333

Sample Output

1 1

2 0

22 -2

58 -3

278 -3

1655470 2

题目分析

杜教筛模板题。（垃圾卡常题）

套套路即可。

代码实现

#include<iostream>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<cstdio>

#include<iomanip>

#include<cstdlib>

#include<map>

#define MAXN 0x7fffffff

typedef long long LL;

const int N=3e6+5,M=3e6;

using namespace std;

inline int Getint(){register int x=0,f=1;register char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}return x*f;}

int prime[N];

bool vis[N];

int mu[N];

map<int,int>smu;

int Smu(int x){

	if(x<=M)return mu[x];

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

	int ret=1;

	for(int l=2,r=0;r!=x;l=r+1){

		r=x/(x/l);

		ret-=1ll*(r-l+1)*Smu(x/l);

	}

	return smu[x]=ret;

} 

LL phi[N];

map<int,LL>sphi;

LL Sphi(int x){

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

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

	LL ret=1ll*x*(1ll*x+1)/2;

	for(int l=2,r=0;r!=x;l=r+1){

		r=x/(x/l);

		ret-=1ll*(r-l+1)*Sphi(x/l);

	}

	return sphi[x]=ret;

} 

int main(){

	phi[1]=mu[1]=1;

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

		if(!vis[i])prime[++prime[0]]=i,mu[i]=-1,phi[i]=i-1;

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

			vis[i*prime[j]]=1;

			if(i%prime[j]==0){

				phi[i*prime[j]]=phi[i]*prime[j];

				break;

			}

			phi[i*prime[j]]=phi[i]*phi[prime[j]];

			mu[i*prime[j]]=-mu[i];

		}

	}

	for(int i=2;i<=M;i++)phi[i]+=phi[i-1],mu[i]+=mu[i-1];

	int T=Getint();

	while(T--){

		int n=Getint();

		cout<<Sphi(n)<<' '<<Smu(n)<<'\n';

	}

	return 0;

}

巴特西

【BZOJ3944】Sum

题面

Description

Input

Output

Sample Input

Sample Output

题目分析

代码实现

最新文章

热门文章