欧拉函数

定义: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))个。
证毕

5. 若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 mid n ,则varphi(n)=varphi(n/p)*(p-1))
证明:
若p|n且(p^2 mid 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
，我们可以有

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

所以可以继续化简

[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}} ]

模板题和代码见P2303 [SDOI2012] Longge 的问题