什么是简化剩余系？

_所有$0<n<=m,(n,m)=1$的n构成了模m的简化剩余系，简称缩系_

记这样n的个数为$ \phi(m)$

相关性质

• 如果$(m,m’)=1$,$a$取遍模$m$缩系,$a’$取遍m’缩系
  那么$am’+a’m$取遍$mm’$缩系

   - $Prove: 已知(a,m)=1,(a',m')=1 , (m,m')=1$
      $(am',m)=1,(a'm,m')=1$
      $(am'+a'm,m)=1,(a'm+am',m')=1$   //加上另一个数的若干倍仍互质
      $(am'+a'm,mm')=1$
   -  所以如果$(n,m)=1,\phi(nm)=\phi(n)*\phi(m)$
  

• • $\phi(p^e)=(p-1)p^{e-1}=p^e(1-1/p) $ p是质数
  • $Prove: [1,p^e]中与p不互质的数的个数为p^e/p=p^{e-1}$

      $\phi(p^e)=p^e-p^{e-1} =p^e*(1-1/p)$
    

    • 特殊地,若$p$是一个质数,则$\phi(p)=p-1$

什么是欧拉函数

_在数论，对正整数$n$，欧拉函数是小于或等于$n$的数中与$n$互质的数的数目。欧拉函数用希腊字母$phi()$或$\phi()$ （念fai去声）表示，$phi(n)$表示正整数n的欧拉函数。_

举个栗子：$[1,12]$中与$12$互质的有$1,5,7,11$。
(别忘了，$a$与$b$互质表示$gcd(a,b)=1$，故1也算)
所以$\phi(12)=4$。

很显然这个$\phi(m)$就是上文简化剩余系中所提到的

欧拉函数的计算

由上文简化剩余系的性质可知

计算公式:$\phi(p)= \prod \phi(p_i^{c_i}) = \prod (p^c_i (1-1/p_i)) = n \prod (1-1/p_i)$

计算方式

直接按照定义

1
2
3
4
5
6
7
8
9
10
11
12
13

int euler_phi(int n){
	int m=(int)sqrt(n+0.5);
	int ans=n;
	for(register int i=2;i<=m;i++)
		if(n%i==0)
		{//最好要先除后乘，防止结果溢出
		  ans=ans/i*(i-1);   //上文推导得 
		  while(n%i==0)n=n/i;//将n中所有因子i筛去 
		                   //确保下一个i是n的质因子 
		}
	if(n>1)ans=ans/n*(n-1);//防止n为最后一个质因子 
	return ans;
}

例题： hdu 1787裸欧拉函数简单变式

有没有$O(N)$预处理出一张欧拉函数表的方法呢？当然有,在欧拉筛的基础上稍加改动即可，想要看懂代码请您先熟练欧拉筛

这是一个欧拉筛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

void Euler_Prime() 
{ 
  memset(is_Prime,1,sizeof(is_Prime));
  memset(pri,0,sizeof(pri)); 
  is_Prime[0]=0;
  is_Prime[1]=0;//特判
   for(register int i=2;i<=n;i++) { 
      if(is_Prime[i]) 
        pri[tot++]=i;   //----1
      for(register int j=0; j<tot && i*pri[j]<=n;j++){ 
         is_Prime[i*pri[j]]=0; 
         if(i%pri[j]==0) break; //-----2
         //-----3
      } 
   }  
}

使用欧拉筛时无非在代码中$1,2,3$处三种情况:

（话说第二条的证明找了挺久，好多人都直接略过，感觉我真的太菜了

1. 判定$i$是一个质数,根据上文性质$\phi(i)=i-1$

2. 在2处,$\phi(ipri[j])=\phi(i)pri[j]$

   $Prove:$设$x=pri[j]*i$,易知此时$i$包含$pri[j]$这个质因子,即$i$的质因子与$x$的相同,根据欧拉函数的直接计算方式,

   $\phi(x)=x \prod (1-1/p_i)=pri[j]i \prod (1-1/p_i)= pri[j]\phi(i)$

3. 在3处,易知$i$与$pri[j]$互质,根据欧拉函数性质(也是积性函数性质)

   $\phi(x) = \phi(i)\phi(pri[j]) = \phi(i) (pri[j]-1)$

然后就可以看懂代码了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

inline void get_phitable(){
	bool is_pri[maxn];
	int num[1000005],tot=0,tmp;
	memset(is_pri,0,sizeof(is_pri));
	is_pri[1]=1;
	phi[1]=1;
	for(ri i=2;i<=maxn;i++){
	    //printf("%d\n",i);
		if(!is_pri[i]){
			num[++tot]=i;
			phi[i]=i-1;
		}
		for(ri j=1;j<=tot;j++){
			tmp=num[j]*i;
			if(tmp>=maxn)break;
			is_pri[tmp]=1;
			if(i%num[j]==0){
				phi[tmp]=num[j]*phi[i];
				break;
			}
			else {
				phi[tmp]=(num[j]-1)*phi[i];
			}
		}
	}
	return ;
}

推荐阅读