欧拉函数

欧拉函数：
就是对于一个正整数n，小于n且和n互质的正整数（包括1）的个数，记作φ(n) 。

欧拉函数的通式：φ(n)=n*(1-1/p1)(1-1/p2)(1-1/p3)*(1-1/p4)……(1-1/pn)
其中p1, p2……pn为n的所有质因数，n是不为0的整数。φ(1)=1（唯一和1互质的数就是1本身）。

题目：https://www.acwing.com/problem/content/875/

代码：

#include<iostream>
#include<cstdio>
using namespace std;
int n;
int a[110];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}	
	for(int i=1;i<=n;i++){
		int ans=a[i];
		for(int j=2;j*j<=a[i];j++){
			if (a[i]%j==0) ans=ans/j*(j-1);//先除再乘，否则结果是0 
			while(a[i]%j==0){
				a[i]/=j;	
			}
		}
		//cout<<a[i]<<endl;
		if(a[i]>1) ans=ans/a[i]*(a[i]-1);//最后a[i]是质数的情况 
		printf("%d
",ans);
	}
	return 0;
	
}

该算法的时间复杂度比较高，当数据量比较大时，可以先用线性筛求出所有的素数，再求欧拉函数

874. 筛法求欧拉函数（https://www.acwing.com/problem/content/876/）

给定一个正整数

输入格式

共一行，包含一个整数

输出格式

共一行，包含一个整数，表示

数据范围

输入样例：

输出样例：

/*
“最小质因数 × 最大因数（非自己） = 这个合数”
每个数的最小质因数和最大因数是唯一的，所以每个数只被筛一次
时间复杂度为 O(n)*/ 
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=1e6+10;
int vis[maxn],Prime[maxn],phi[maxn];
int main(){
	int n,cnt=0,q;
	scanf("%d",&n);
	phi[1]=1;
	for(int i=2;i<=n;i++) {//边筛边求欧拉函数 
		if(!vis[i]) {
			Prime[++cnt]=i; //如果没被筛掉，说明没有因子，则一定是质数 
			phi[i]=i-1;
		}
		for(int j=1;Prime[j]<=n/i;j++){
			vis[i*Prime[j]]=1;//i是最大因数，prime[j]是最小质因数 
			if(i%Prime[j]==0) {
				phi[i*Prime[j]]=Prime[j]*phi[i];// i*Prime[j]的质因子和i是完全一样的。因为多了个prime[j]所以乘上 
				break;//如果prime[j]是i的最小质因数，则退出当前循环。
			} 
			phi[i*Prime[j]]=phi[i]*(Prime[j]-1);//i*Prime[j]的质因子有i的质因子和prime[j],phi[i*Prime[j]]=Prime[j]*phi[i]/prime[j]*(prime[j]-1)=phi[i]*prime[j-1]  
		}//如i=9,prime[j]=3，prime[j+1]=5 ,9*5 =15*3=45所以45的最大因数是15，而不是9，故i%Prime[j]==0时必须退出循环 
	}
	long long ans=0;
	for(int i=1;i<=n;i++) {
		ans+=phi[i];
	//	cout<<phi[i]<<endl;
	}
	printf("%lld
",ans);
	return 0;
}

欧拉函数的一些性质：
① 当m,n互质时，有phi（m*n）= phi（m）*phi（n）；

② 若i%p==0，有phi（i*p） = p * phi(i)；

③ 对于互质x与p，有x^phi§≡1（mod p),因此x的逆元为x^(phi§-1)，即欧拉定理。
（特别地，当p为质数时，phi（p）=p-1,此时逆元为x^(p-2)，即费马小定理）

④ 当n为奇数时，phi(2n)=phi(n)

⑤ 若x与p互质，则p-x也与p互质，因此小于p且与p互质的数之和为phi(x)*x/2;

⑥N>1，不大于N且和N互素的所有正整数的和是 1/2 *N *eular(N)。

⑦若(N%a == 0 && (N/a)%a==0) 则有:E(N)=E(N/a)*a;

⑧若(N%a==0 && (N/a)%a!=0) 则有:E(N)=E(N/a)*(a-1);
————————————————
参考：CSDN博主「浦柳人」，链接：https://blog.csdn.net/weixin_43237242/article/details/97388834