欧拉函数的性质

定义

$\phi(n)表示在1-n中与n互质的数$

两种计算方式

• $\phi(n)=n*\prod_{p|n}(1-\frac{1}{p})$
• 线性筛(边筛边递推)

  性质1

  $$\phi(p^k) = (p-1)*p^{k-1}$$ $\because p^k只有一个因数p,p^k与他不互质的数只有p^k/p=p^{k-1}个$

$\therefore \phi(p^k)=p^k-p^{k-1}$

性质2

$若P|n$

$$\phi(P*n) = P*\phi(n)$$

$若!P|n$

$$\phi(P*n) = (P-1)*\phi(n)$$

$\because \phi(n)=n*\prod_{p|n}(1-\frac{1}{p})$

$\phi(P)=P*\prod_{p|P}(1-\frac{1}{p})$

$\therefore P|n$

$$\phi(P*n) = n*P*\prod_{p|P*n}(1-\frac{1}{p})=\phi(P)*\phi(n)$$

$\therefore !P|n$

$$\phi(P*n) = P*n*\prod_{p|P*n}(1-\frac{1}{p})=P*\phi(n){P与n的因数相交}$$

$也可以证明为gcd(a,b)=1$

$$\phi(a*b)=\phi(a)*\phi(b)$$

根据以上性质就可以在线性筛 递推

if (i % prime[j])
    ph[i * prime[j]] = ph[prime[j]] * ph[i];
else
    {
        ph[i * prime[j]] = ph[i] * prime[j];
        break;
    }

性质3

$$\sum_{d|n}\phi(d)=n$$

$\because 设f(n)=\sum_{d|n}\phi(d)$
$若gcd(n,m)=1$

$$f(m)f(n)=\sum_{d|n}\phi(d)\sum_{d|m}\phi(d)=\sum_{d|nm}\phi(d)=f(nm)$$ $$\because f(n)=f(p_1^{c_1})*f(p_2^{c_2})*f(p_3^{c_3})...f(p_m^{c_m})$$ $$f(p^k)=\phi(1)+\phi(p)+\phi(p^2)+...\phi(p^{k-1})=1+p-1+p^2-p...p^k-p^{k-1}=p^k$$

$\therefore f(n)=n$

应用

计算

$$f(n)=\sum_{i=1}^{n}\phi(i)(n<=1e10)$$ $$\sum_{i=1}^{n}\sum_{d|n}\phi(d)=(n)*(n+1)/2$$

$分析d出现次数=n/d,所以枚举d$

$$\sum_{d=1}^{n}\sum_{i=1}^{n/d}\phi(d)=(n)*(n+1)/2=\sum_{d=1}^{n}f(\frac{n}{d})=f(n)+\sum_{d=2}^{n}f(\frac{n}{d})$$ $$f(n)=(n)*(n+1)/2-\sum_{d=2}^{n}f(\frac{n}{d})$$ $$分块,对于f(\frac{n}{d})很多相同,在枚举时,f(\frac{n}{l})*(r-l+1)(r=\frac{n}{\frac{n}{l}})$$ $$预处理n<=5e6,使用线性筛$$ $$复杂度(n^{\frac{2}{3}})$$