欧拉函数

定义:1~N中与N互质的数的个数，记为\(\varphi (N) 或 phi(N)\)
积性函数:如果当a，b互质，有f(ab)=f(a)*f(b),则称函数f是积性函数。

性质

  1. 欧拉函数是积性函数（这里写得更好https://www.zhihu.com/question/410737433)
    证明：
    引理:

\[ m=m_1 m_2,m_1 \perp m_2,则有 \\ n \perp m \Leftrightarrow (n \ mod \ m_1) \perp m_1,( n \ mod \ m_2 ) \perp m_2 \\ 显然 n \perp m \Leftrightarrow n \perp m_1,n \perp m_2 \\ 而 gcd(n,m_1)=gcd(m_1,n \ mod m_1) ，故引理得证。 构造m关于模m_1,m_2的剩余系，可证 \varphi(m_1m_2)=\varphi(m_1) \varphi(m_2) \]

证毕

2.\(\varphi(1)=1,\varphi(p)=p-1,p是素数\)
3.欧拉函数计算式

\[根据性质1和唯一分解定理，可得欧拉函数的计算式 \\ \varphi(n)=\varphi(\prod _{i=1}^{m} p_i^{c_i} )=\prod _{i=1}^{m} \varphi(p_i^{c_i})=\prod _{i=1}^{m} (p_i^{c_i}-p_i^{c_i-1}) \\ 解释一下，p是质数，\varphi(p^c)是[1,p^c]里与p^c互质的数的个数，与p^c不互质的数有p,2p,3p,\cdots,p^{c-1},一共p^{c-1}个 (或者可以理解为p^c / p个)\\ =\prod _{i=1}^{m} p_{i}^{c_i}(1-\frac{1}{p_i})=n \prod _{i=1}^{m} (1-\frac{1}{p_i}) \]

因此，我们可以得出快速求某个数n欧拉函数值的方法，对n进行质因数分解，下面是模板

inline int phi(int n) {
	int ans = n;
	int t = sqrt(n);
	rep(i, 2, t) {
		if(n % i == 0) {
			ans = ans / i * (i - 1)；
			      while(n % i == 0) n /= i;
		}
		if(n > 1) ans = ans / n * (n - 1);
		return ans;
	}
}

4.\(\forall n>1,1~n中与n互质的数和为n * \varphi(n)/2\)
证明:
因为gcd(n,x)=gcd(n,n-x),所以与n不互质的数x,n-x是成对出现的，平均值为n/2，因此，与n互质的数的平均值也是n/2，共\(\varphi(n)\)个。
证毕

  1. 若p|n,且\(p^2|n,则\varphi(n)=\varphi(n/p)*p\)
    证明:
    因为p|n,\(p^2|n\) ,所以n，n/p包含了相同的质因子\(p^?\)，只是指数不同。将$ \varphi(n),\varphi(n/p) 按照欧拉函数计算式写出，相除的商为p$
    证毕

6.若p|n且\(p^2 \nmid n ,则\varphi(n)=\varphi(n/p)*(p-1)\)
证明:
若p|n且\(p^2 \nmid n\),所以p和n/p互质，所以\(\varphi(n)=\varphi(n/p)*\varphi(p),\varphi(p)=p-1\)
证毕
7. $$ \sum_{d|n}\varphi(d)=n $$

证明：
设
\(f(n)=\sum _{d|n}\varphi(d)\)
设m，n互质,则有
\(f(nm)=\sum _{d \mid nm} \varphi(d) =\sum _{a|n,b|m} \varphi(ab)=\sum _{a|n,b|m} \varphi(a) \varphi(b)=(\ \sum _{a|n} \varphi(a) \ ) * (\ \sum _{b|m} \varphi(b) \ )\)
所以f（n)也是积性函数。对于单个质因子\(f(p^m)=\sum _{d|p^m} \varphi(d)=\varphi(1)+\varphi(p)+\varphi(p^2)+\cdots+\varphi(p^m)\)
是一个等比数列求和后再加1，公比为p。结果为\(p^m\)。所以\(f(n)=\prod _{i=1}^{m}f(p_i^{c_i})=\prod _{i=1}^{m}p_i^{c_i}=n\)
得证

8.若n为奇数，\(\varphi(2n)=\varphi(n)\)。
证明:因为n为奇数,所以\(n \perp 2 ,\varphi(2n)=\varphi(n)*\varphi(2)，而\varphi(2)=1\)
证毕

求法:1.分解质因数，上文有写
2.适用与求[1,N]中所有数的欧拉函数值，用质数筛的思想

（1）埃氏筛，时间复杂度O（N log N)
inline void Euler(int n){
   rep(i,1,n) phi[i]=i;
   rep(i,2,n){
   	if(phi[i]==i)//  i是质数， 
   	 {
   	for(register int j(i);j<=n;j+=i)	
   		phi[j]=phi[j]/i*(i-1);
   	}
   }
} 

(2)欧拉筛，我们可以根据性质5和6来边进行欧拉筛边计算被筛除的数的欧拉函数值，时间复杂度为O（N）
int v[MAXX], prime[MAXX], phi[MAXX], cnt;
inline void EulerSieve(int N) {
	memset(v, 0, sizeof v); //最小质因子
	cnt = 0;
        phi[1]=1;
	rep(i, 2, N) {
		if(!v[i]) {
			v[i] = i;
			prime[++cnt] = i;
			phi[i] = i - 1;
		}
		rep(j, 1, cnt) {
			if(prime[j] > v[i] || 1ll * prime[j]*i > 1ll * N) break;
			v[i * prime[j]] = prime[j];
			phi[i * prime[j]] =phi[i]*  (i % prime[j] ? prime[j] - 1 : prime[j] );
		}
	}
}

欧拉反演
(以下公式和部分内容搬运于粉兔,自己懒得打了，加了点注释)
利用上面性质7
，我们可以有

\[\begin{align} \sum_{i=1}^{n} \operatorname{gcd}(i, n) &=\sum_{j=1}^{n}\left(j \times \sum_{i=1}^{n}[g c d(i, n)=j]\right) (枚举gcd) \\ &=\sum_{j=1}^{n}\left(j \times \sum_{i=1}^{n}[g c d(i / j, n / j)=1](j|i, j| n)\right) (i/j 会小于等于 n/j) \\ &=\sum_{j=1}^{n}(j \times \varphi(n / j)(j \mid n)) \\ &=\sum_{j \mid n}(j \times \varphi(n / j)) \\ &到这里就可以直接计算了。 但是还可以进一步化简! (以下的 p 为质数) \\ \\ &=\sum_{j \mid n}(n / j \times \varphi(j)) （变量替换）\\ &=\sum_{j \mid n}\left(n / j \times\left(j \cdot \prod_{p \mid j} \frac{p-1}{p}\right)\right) (欧拉函数的直接计算式)\\ &=\sum_{j \mid n}\left(n \cdot \prod_{p \mid j} \frac{p-1}{p}\right) \\ &=n \times \sum_{j \mid n} \prod_{p \mid j} \frac{p-1}{p} \\ \end{align} \]

\[n=p_1^{b_1} p_2^{b_2} \cdots p_k^{b_k} \\ 所以 j=p_1^{c_1} p_2^{c_2} \cdots p_k^{c_k} ( 0 \le c_i \le b_i ) \\ f_i=\frac{p_i-1}{p_i} \]

\[\prod_{p \mid j} \frac{p-1}{p}=\prod_{i=1}^{k} f_{i}\left[c_{i}>0\right] \]

所以可以继续化简

\[n * \prod_{i=1}^k(f_i*b_i+1)(可以取，也可以不取) \]

最后

\[n \cdot \prod_{i=1}^{k} \frac{b_{i} \cdot p_{i}-b_{i}+p_{i}}{p_{i}} \]

模板题和代码见

数论欧拉函数

相关

标签