欧拉函数

定义

欧拉函数(Euler’s totient function),即 φ\varphi,表示的是小于等于 nnnn 互质的数的个数。

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

nn 是质数的时候,显然有 φ(n)=n1\varphi(n) = n - 1

计算

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

φ(N)=N×p11p1××pm1pm=NpN(11p)     (pPrime)\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)

证明
ppNN 的质因子, 1N1 \sim Npp 的倍数有 p,2p,3p,,(Np)pp,2p,3p,\cdots,(\lfloor \frac{N}{p} \rfloor)pNp\lfloor \frac{N}{p} \rfloor 个。同理,若 qq 也是 NN 的质因子,则 1N1 \sim Nqq 的倍数有 Nq\lfloor \frac{N}{q} \rfloor个。如果我们把这 Np+Nq\lfloor \frac{N}{p} \rfloor + \lfloor \frac{N}{q} \rfloor 个书去掉,那么 pqpq 的倍数被排除了两侧,需要加回来一次(容斥原理)。因此 , 1N1 \sim N 中不与 NN 含有任何共同质因子 qqpp 的个数为:

NNpNq+Npq=N(11p1q+1pq)=N(11p)(11q)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})

类似的,可以对 NN 的所有质因子进行上述操作即可得到 φ(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;
}

性质

基本性质

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

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

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

证毕。

积性函数

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

其他性质

  1. ff 为积性函数,且在算数基本定理中 n=i=1mpicin = \prod_{i=1}^m p_i^{c_i},则 f(n)=n=i=1mf(pici)f(n) = n = \prod_{i=1}^m f(p_i^{c_i})
  2. pp 为质数,若pnp\mid np2np^2 \mid n ,则 φ(n)=φ(n/p)p\varphi(n) = \varphi(n/p) \cdot p
  3. pp 为质数,若pnp\mid np2np^2 \nmid n ,则 φ(n)=φ(n/p)(p1)\varphi(n) = \varphi(n/p) \cdot (p - 1)
  4. dnφ(d)=n\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; //保证只筛一次
        }
    }
}