欧拉函数

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

欧拉函数的计算

  • 若$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}}$,由于欧拉函数是积性函数(在后面给出证明),所以得出计算式

    欧拉函数是积性函数

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

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

线性筛欧拉函数的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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 ;
}
}
}
}