欧拉函数

一个数的欧拉函数，是指小于这个数且与这个数互质的数的总数。

$$\phi(x) = \sum_{i=1}^{n}[(x,i)=1]$$

欧拉函数的计算

• 若$x$是质数，$\phi(x) = x-1$
• 进一步，若$x = a^p$ ( $a$是质数)
  不难发现，如果某数不包含$a$这个质因子，那么一定与$x$互质，而$\forall a^i \ (1 \le i \lt p)$都包含$a$，减去即可。$\phi(x) = a^p-a^{p-1} = a^p(1-\frac{1}{a})$

• 进而，设$x = \sum_{i=1}^{m}{p_i^{a_i}}$，由于欧拉函数是积性函数(在后面给出证明)，所以得出计算式

  $$\begin{equation} \phi(x) = \quad \Pi_{i=1}^{m}{\phi(p_i^{a_i})} = \quad \Pi_{i=1}^{m}{p_i^{a_i} \times (1-\frac{1}{p_i})} = \quad x \\ \Pi_{i=1}^{m}{1-\frac{1}{p_i}} \end{equation}$$

  欧拉函数是积性函数

  已知$(n,m)=1$，求证$\phi(nm)=\phi(n) \times \phi(m)$
  不妨绘制一张如下的表格

  $$\begin{matrix} 1 & 2 & \cdots & r & \cdots & m \\\\ m+1 & m+2 & \cdots & m+r & \cdots & 2*m \\\\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\\\ (n-t)m+1 & (n-t)m+2 & \cdots & (n-t)m+r & \cdots & (n-t+1)m \\\\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\\\ (n-1)m+1 & (n-1)m+2 & \cdots & (n-1)m+r & \cdots & nm \\\\ \end{matrix}$$

  求这张表格里与$nm$互质的数的个数。
  不难发现，每一行对$m$取模的结果构成了$0$ ~ $m-1$的一个排列，每一列对$n$取模的结果构成了$0$ ~ $n-1$的一个排列。
  所以，与$nm$互质的数只存在于共$\phi(m)$行模$m$余数与$m$互质的行里，且在共$\phi(n)$列模$n$余数与$n$互质的列里。
  共$\phi(n) \times \phi(m)$个数。

线性筛欧拉函数的代码

int n, m, cnt, phi[maxn], pr[maxn] ;
bool isp[maxn] ;
void _init() {
    int i, j ;
    memset ( isp, 1, sizeof isp ) ;
    isp[1] = 0 ;
    phi[1] = 1 ;
    for ( i = 2 ; i < maxn ; i ++ ) {
        if (isp[i]) {
            phi[i] = i-1 ;
            pr[++cnt] = i ;
        }
        for ( j = 1 ; j <= cnt && pr[j]*i < maxn ; j ++ ) {
            isp[i*pr[j]] = 0 ;
            if (i%pr[j]) phi[i*pr[j]] = phi[i]*phi[pr[j]] ;
            else {
                phi[i*pr[j]] = phi[i]*pr[j] ;
                break ; 
            } 
        }
    }
}