欧拉函数

定义

欧拉函数（Euler’s totient function），即 $\varphi$ ，表示的是小于等于 $n$ 和 $n$ 互质的数的个数。

$e.g. \ \ \ \varphi(1) = 1$

当 $n$ 是质数的时候，显然有 $\varphi(n) = n - 1$ 。

计算

若在算数基本定理中， $N = p_1^{c_1}p_2^{c_2}\cdots p_m^{c_m}$

\varphi(N) = N \times \frac{p_1 - 1}{p_1} \times \cdots \times \frac{p_m - 1}{p_m} = N * \prod_{p | N} (1-\frac{1}{p}) \ \ \ \ \ (p \in Prime)

证明：
设 $p$ 是 $N$ 的质因子, $1 \sim N$ 中 $p$ 的倍数有 $p,2p,3p,\cdots,(\lfloor \frac{N}{p} \rfloor)p$ 共 $\lfloor \frac{N}{p} \rfloor$ 个。同理，若 $q$ 也是 $N$ 的质因子，则 $1 \sim N$ 中 $q$ 的倍数有 $\lfloor \frac{N}{q} \rfloor$ 个。如果我们把这 $\lfloor \frac{N}{p} \rfloor + \lfloor \frac{N}{q} \rfloor$ 个书去掉，那么 $pq$ 的倍数被排除了两侧，需要加回来一次（容斥原理）。因此， $1 \sim N$ 中不与 $N$ 含有任何共同质因子 $q$ 或 $p$ 的个数为：

N - \frac{N}{p} - \frac{N}{q} + \frac{N}{pq} = N(1 - \frac{1}{p} - \frac{1}{q} + \frac{1}{pq}) = N(1-\frac{1}{p})(1-\frac{1}{q})

类似的，可以对 $N$ 的所有质因子进行上述操作即可得到 $\varphi(N)$

证毕。

故，我们只需分解质因数，即可顺利求出欧拉函数。


int Phi(int n) {
    int Ans = n;
    for(int i = 2; i <= sqrt(n); i++) {
        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;
}

性质

基本性质

$\forall n > 1,1 \sim n$ 中与 $n$ 互质的数的和为 $\frac{\varphi(n) \cdot n}{2}$
若 $gcd(a,b) = 1$ ，则 $\varphi(ab) = \varphi(a)\varphi(b)$

证明：
因为 $gcd(n,m) = gcd(n ,n - x)$ ，所以与 $n$ 互质的数成对出现，每对的和为 $n$ ，共有 $\frac{\varphi(n)}{2}$ 对，所以和为 $\frac{\varphi(n) \cdot n}{2}$ ，性质 $1$ 显然成立

根据欧拉函数的计算式,对 $a,b$ 分解质因数，可以得到性质 $2$ 。即为 欧拉函数是积性函数

证毕。

积性函数

如果 $gcd(a,b) = 1$ ，有 $f(ab) = f(a)f(b)$ ，那么称函数 $f$ 为积性函数。

其他性质

若 $f$ 为积性函数，且在算数基本定理中 $n = \prod_{i=1}^m p_i^{c_i}$ ，则 $f(n) = n = \prod_{i=1}^m f(p_i^{c_i})$
设 $p$ 为质数，若 $p\mid n$ 且 $p^2 \mid n$ ，则 $\varphi(n) = \varphi(n/p) \cdot p$
设 $p$ 为质数，若 $p\mid n$ 且 $p^2 \nmid n$ ，则 $\varphi(n) = \varphi(n/p) \cdot (p - 1)$
$\sum_{d \mid n} \varphi(d) = n$

线性筛

由于欧拉函数是积性函数，所以可以线性筛，代码见下

for(int i = 2; i <= n; i++) {
    if(!vis[i]) {    //i是质数
        prime[primen++] = i;
        phi[i] = i - 1;  //质数的欧拉函数是比它少一
    }
    for(int j = 0; j < primen; j++) {
        if(i*prime[j] > n) break;
        vis[i*prime[j]] = 1;
        if(i % prime[j] != 0) 
            //积性函数
            phi[i*prime[j]] = phi[i] * phi[prime[j]];
        else{
            //若x是质数p的倍数，则phi[x]=phi[x/p]*p
            phi[i*prime[j]] = phi[i] * prime[j];
            break; //保证只筛一次
        }
    }
}