欧拉函数和莫比乌斯函数的求法

1.欧拉函数性质和求法：https://blog.csdn.net/yxuanwkeith/article/details/52387873
两种方法：

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long LL;
int phi[1000005],prime[1000005];
bool f[100005];
LL getphi(LL n) {
	LL phi=n;
	for (LL i=2;i*i<=n;i++) {
		if (n%i==0) {
			phi=phi/i*(i-1);
			while (n%i==0) n/=i;
		}
	}
	if (n>1) phi=phi/n*(n-1);
	return phi;
}
int main() {
	int n;
	cin>>n;
	
	cout<<getphi(n)<<endl;
	
	phi[1]=1;
	for (LL i=2;i<=n;i++) {
		if (!f[i]) {
			phi[i]=i-1;
			prime[++prime[0]]=i;
		}
		for (int j=1;j<=prime[0];j++) {
			if (i*prime[j]>n) break;
			f[i*prime[j]]=1;
			if (i%prime[j]==0) {
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}
			else phi[i*prime[j]]=phi[i]*(prime[j]-1);
		}
	}
	
	for (int i=1;i<=n;i++) cout<<phi[i]<<' ';cout<<endl;
	return 0;
}

2.莫比乌斯函数 https://www.cnblogs.com/Milkor/p/4464515.html
两种方法：

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long LL;
int miu[1000005],prime[1000005];
bool f[100005];
LL getmiu(int n) {
	int s=0;
	for (LL i=2;i*i<=n;i++) {
		if (n%i==0) {
			s++;
			int cnt=0;
			while (n%i==0) n/=i,cnt++;
			if (cnt>=2) return 0;
		}
	}
	if (n>1) s++;
	if (s&1) return 1;
	else return 0;
}
int main() {
	int n;
	cin>>n;
	
	cout<<getmiu(n)<<endl;
	
	miu[1]=1;
	for (LL i=2;i<=n;i++) {
		if (!f[i]) {
			miu[i]=-1;
			prime[++prime[0]]=i;
		}
		for (int j=1;j<=prime[0];j++) {
			if (i*prime[j]>n) break;
			f[i*prime[j]]=1;
			if (i%prime[j]==0) {
				miu[i*prime[j]]=0;
				break;
			}
			else miu[i*prime[j]]=-miu[i];
		}
	}
	
	for (int i=1;i<=n;i++) cout<<miu[i]<<' ';cout<<endl;
	return 0;
}