代码仓库：欧拉筛板欧拉函数递推

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<deque>
#include<cstdlib>
#include<ctime>
#define dd double
#define ld long double
#define ll long long
#define int long long
#define ull unsigned long long
#define N 20000000
#define M number
using namespace std;

const int INF=0x3f3f3f3f;

inline ll read(){
	ll 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*10+ch-‘0‘;ch=getchar();}
	return x*f;
}

int phi[N],prime[N],tail;
bool vis[N];
int n,ans=1;

inline void prework(){
	phi[1]=1;
	for(int i=2;i<=n;i++){
		if(!vis[i]) prime[++tail]=i,phi[prime[tail]]=i-1,ans+=i-1;
		for(int j=1;j<=tail&&i*prime[j]<=n;j++){
			vis[i*prime[j]]=1;
			if(i%prime[j]==0){
				phi[i*prime[j]]=phi[i]*prime[j];
				ans+=phi[i*prime[j]];
				break;
			}
			else phi[i*prime[j]]=phi[i]*phi[prime[j]],ans+=phi[i*prime[j]];
		}
	}
}

signed main(){
	n=read();
	prework();
	printf("%lld",ans);
	return 0;
}

代码仓库：欧拉筛板欧拉函数递推

原文：https://www.cnblogs.com/TianMeng-hyl/p/14643111.html