若 n 是素数 p 的 k 次幂,φ(n)=p^k-p^(k-1)=(p-1)p^(k-1),因为除了 p 的倍数外,其他数都跟 n 互质
欧拉函数是积性函数——若 m,n 互质,φ(mn)=φ(m)φ(n)
3 特殊性质
当 n 为奇数时,φ(2n)=φ(n)
p 是素数,φ(p) = p - 1,φ(p) 称为 p 的欧拉值
若 a 为素数,b mod a=0,φ(a*b)=φ(b)*a
4 模板
//直接法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
intEuler(intn){intres=n,i;//由于任何一个合数都至少有一个不大于根号 n 的素因子,所以只要遍历到根号 n 即可
for(i=2;i*i<=n;i++)if(n%i==0){//第一次找到的必为素因子
n/=i;res=res-res/i;//x(1-1/p1)
while(n%i==0)n/=i;//将该素因子的倍数也全部筛掉
}if(n>1)res=res-res/n;returnres;}
#include<stdio.h>#define N 1000005
#define ll long long
intm[N]={1,1,0};intp[100000],cnt=0;intmax(intx,inty){returnx>y?x:y;}voidprime(){for(inti=2;i<N;i++)if(!m[i]){for(intj=2*i;j<=N;j+=i)m[j]=1;p[cnt++]=i;}}intbinary_search(intx){//二分查找
intl=0,r=cnt;while(l<=r){intmid=(l+r)/2;if(p[mid]>x)r=mid-1;elsel=mid+1;}for(inti=max(r,0);;i++)if(p[i]>x)returnp[i];}intmain(){prime();intT,n,cas=1,temp;scanf("%d",&T);while(T--){scanf("%d",&n);llsum=0;for(inti=0;i<n;i++){scanf("%d",&temp);sum+=binary_search(temp);}printf("Case %d: %lld Xukha\n",cas++,sum);}return0;}