浅谈杜教筛

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#define int long long
using namespace std;
const int NN=5000000;
namespace AE86{
	auto read=[](){
		int x=0,f=1;char ch=getchar();
		while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
		while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
		return x*f;
	};
}using namespace AE86;
int T,n,mu[NN+5],len,prime[NN+5];
int phi[NN+5];
auto getprime=[](){
	mu[1]=1; phi[1]=1;
	for(int i=2;i<=NN;i++){
		if(!phi[i]) prime[++len]=i,mu[i]=-1,phi[i]=i-1;
		for(int j=1;j<=len&&prime[j]*i<=NN;j++){
			if(i%prime[j]==0){
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}
			mu[i*prime[j]]=-mu[i];
			phi[i*prime[j]]=phi[i]*(prime[j]-1);
		}
	}
	for(int i=1;i<=NN;i++) mu[i]+=mu[i-1],phi[i]+=phi[i-1];
};
unordered_map<int,int>smu;
unordered_map<int,int>sphi;
inline int getmu(int n){
	if(n<=NN) return mu[n];
	if(smu.find(n)!=smu.end()) return smu[n];
	int res=1,l=2,r;
	while(l<=n){
		r=n/(n/l);
		res-=(r-l+1)*getmu(n/l);
		l=r+1;
	} return smu[n]=res;
}
inline int getphi(int n){
	if(n<=NN) return phi[n];
	if(sphi.find(n)!=sphi.end()) return sphi[n];
	int res=(1+n)*n/2;int l=2,r;
	while(l<=n){
		r=n/(n/l);
		res-=(r-l+1)*getphi(n/l);
		l=r+1;
	} return sphi[n]=res;
}
namespace WSN{
	inline short main(){
		T=read(); getprime();
		while(T--){
			n=read();
			printf("%lld %lld\n",getphi(n),getmu(n));
		}
		return 0;
	}
}
signed main(){return WSN::main();}

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#define int long long
using namespace std;
const int NN=5000005;
int n,mod,v6,v2,ans;
namespace AE86{
	auto read=[](){
		int x=0,f=1;char ch=getchar();
		while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
		while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
		return x*f;
	};
	auto write=[](int x,char opt='\n'){
		char ch[20];short len=0;if(x<0)x=~x+1,putchar('-');
		do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x);
		for(short i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);
	};
	auto qmo=[](int a,int b,int ans=1){
		int c=mod;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;
		return ans;
	};
	inline int sig(int n){return (1+n)%mod*n%mod*v2%mod;}
	inline int pws(int n){return (2*n%mod+1)%mod*n%mod*(n+1)%mod*v6%mod;}
	inline int pps(int n){return sig(n)*sig(n)%mod;}
}using namespace AE86;
namespace Prime{
	signed len,prime[NN];
	int phi[NN],F[NN];
	bool vis[NN];
	auto getprime=[](){
		phi[1]=1; F[1]=1;
		for(signed i=2;i<NN;++i){
			if(!vis[i]) prime[++len]=i,phi[i]=i-1;
			for(signed j=1;j<=len&&prime[j]*i<NN;++j){
				vis[i*prime[j]]=1;
				if(!(i%prime[j])){phi[i*prime[j]]=phi[i]*prime[j];break;}
				phi[i*prime[j]]=phi[i]*(prime[j]-1);
			}
			F[i]=(phi[i]*i%mod*i%mod+F[i-1])%mod;
		}
	};
}using namespace Prime;
namespace dujiao_shai{
	unordered_map<int,int>sF;
	inline int getF(int n){
		if(n<NN) return F[n];
		if(sF[n]) return sF[n];
		int res=pps(n);
		for(int l=2,r;l<=n;l=r+1) r=n/(n/l),
			res=(res-(pws(r)-pws(l-1)+mod)%mod*getF(n/l)%mod+mod)%mod;
		res=(res%mod+mod)%mod;
		return sF[n]=res;
	}
}using namespace dujiao_shai;
namespace WSN{
	inline short main(){
		mod=read();n=read();getprime();
		v6=qmo(6,mod-2);v2=qmo(2,mod-2);
		for(int l=1,r;l<=n;l=r+1) r=n/(n/l),
			ans=(ans+(getF(r)-getF(l-1)+mod)%mod*pps(n/l)%mod)%mod;
		write(ans);
		return 0;
	}
}
signed main(){return WSN::main();}