欧拉函数 笔记

看着书上的定理，自己亲手证明。

定义

$\mathrm{\forall }a,b\in \mathbb{N}\backslash forall\; a,\; b\; \backslash in\; \backslash mathbb\{N\}$，若 $\gcd (a,b)=1\backslash gcd(a,\; b)\; =\; 1$，则称 $a,ba,\; b$ 互质。

定义 $11$ 到 $nn$ 中与 $nn$ 互质的数的个数为欧拉函数，记作 $\phi (n)\backslash varphi(n)$。

计算式

若在唯一分解定理中，$n=p_1^{c_1}{p}_2^{c_2}\cdots p_m^{c_m}n\; =\; p\_1^\{c\_1\}p\_2^\{c\_2\}\backslash cdots\; p\_m^\{c\_m\}$，则 $\phi (n)=n{\prod }_{i=1}^m(1-\frac{1}{p_i})\backslash varphi(n)\; =\; n\backslash prod\_\{i=1\}^m(1-\backslash frac1\{p\_i\})$，证明如下：

从最简单的开始。设 p, q 都是 n 的因子，那么 n 以内 p, q 的倍数有 n / p, n / q 个，它们的公倍数有 n / pq 个。根据容斥原理，公倍数被算了两次，要减去一次。推广可得（$i\mathrm{\ne }ji\; \backslash ne\; j$）：

性质

书上六条性质，我改成了四条。

性质1

$\mathrm{\forall }n>1\backslash forall\; n\; >\; 1$，$1\sim n1\; \backslash sim\; n$ 中与 $nn$ 互质的数的和为 $\frac{n\phi (n)}{2}\backslash frac\{n\backslash varphi(n)\}\{2\}$。

证明：

设$1\sim n1\; \backslash sim\; n$ 中与 $nn$ 互质的数的和为 $SS$。

由更相减损术得：

所以不与 n 互质的数成对出现（包括 $00$），且它们的平均值为 $n\mathrm{/}2n\; /\; 2$。

所以：

性质2

若 $\gcd (a,b)=1\backslash gcd(a,\; b)\; =\; 1$，则 $\phi (ab)=\phi (a)\phi (b)\backslash varphi(ab)\; =\; \backslash varphi(a)\backslash varphi(b)$。

证明：

设 $a={\prod }_{i=1}^m{p}_i^{c_i}a\; =\; \backslash prod\_\{i=1\}^m\; p\_i^\{c\_i\}$，$b={\prod }_{i=m+1}^{m+n}{p}_i^{c_i}b\; =\; \backslash prod\_\{i=m+1\}^\{m+n\}\; p\_i^\{c\_i\}$，则 $ab={\prod }_{i=1}^{m+n}{p}_i^{c_i}ab\; =\; \backslash prod\_\{i=1\}^\{m+n\}p\_i^\{c\_i\}$。

则 $\phi (a)=a{\prod }_{i=1}^n(1-\frac{1}{p_i})\backslash varphi(a)\; =\; a\backslash prod\_\{i=1\}^n(1-\backslash frac\{1\}\{p\_i\})$，$\phi (b)=b{\prod }_{i=m+1}^{m+n}(1-\frac{1}{p_i})\backslash varphi(b)\; =\; b\backslash prod\_\{i=m+1\}^\{m+n\}(1-\backslash frac\{1\}\{p\_i\})$，$\phi (ab)=ab{\prod }_{i=1}^{m+n}(1-\frac{1}{p_i})\backslash varphi(ab)\; =\; ab\backslash prod\_\{i=1\}^\{m+n\}(1-\backslash frac\{1\}\{p\_i\})$。

而 $\phi (a)\phi (b)=a{\prod }_{i=1}^n(1-\frac{1}{p_i})\times b{\prod }_{i=m+1}^{m+n}(1-\frac{1}{p_i})=ab{\prod }_{i=1}^{m+n}(1-\frac{1}{p_i})\backslash varphi(a)\backslash varphi(b)\; =\; a\backslash prod\_\{i=1\}^n(1-\backslash frac\{1\}\{p\_i\})\; \backslash times\; b\backslash prod\_\{i=m+1\}^\{m+n\}(1-\backslash frac\{1\}\{p\_i\})\; =\; ab\backslash prod\_\{i=1\}^\{m+n\}(1-\backslash frac\{1\}\{p\_i\})$。

所以 $\phi (ab)=\phi (a)\phi (b)\backslash varphi(ab)\; =\; \backslash varphi(a)\backslash varphi(b)$。

推广：

定义积性函数 $f(x)f(x)$ 为满足当 $\gcd (a,b)=1\backslash gcd(a,\; b)\; =\; 1$ 时，$f(ab)=f(a)f(b)f(ab)\; =\; f(a)f(b)$ 的函数。

对于积性函数 $f(x)f(x)$，显然有：

若在算术基本定理中 $x={\prod }_{i=1}^m{p}_i^{c_i}x\; =\; \backslash prod\_\{i=1\}^m\; p\_i^\{c\_i\}$，则 $f(x)={\prod }_{i=1}^{m}f(p_i^{c_i})f(x)\; =\; \backslash prod\_\{i=1\}^m\; f(p\_i^\{c\_i\})$

性质3

设 $pp$ 为质数且 $p\mid np\; \backslash mid\; n$，则有：

证明：

若 $p^2\mid np^2\; \backslash mid\; n$，则 $p\mid (n\mathrm{/}p)p\; \backslash mid\; (n\; /\; p)$。这意味着 $nn$ 和 $n\mathrm{/}pn\; /\; p$ 的质因数集合相同。那么：

即 $\phi (n)=\phi (n\mathrm{/}p)\cdot p\backslash varphi(n)\; =\; \backslash varphi(n\; /\; p)\; \backslash cdot\; p$。

若 $p^2\nmid np^2\; \backslash nmid\; n$ 则 $\gcd (n\mathrm{/}p,p)=1\backslash gcd(n\; /\; p,\; p)\; =\; 1$，根据性质2，有：

性质4

${\sum }_{d\mid n}\phi (d)=n\backslash sum\_\{d\backslash mid\; n\}\; \backslash varphi(d)\; =\; n$。

证明：

设 $f(x)={\sum }_{d\mid x}\phi (d)f(x)\; =\; \backslash sum\_\{d\backslash mid\; x\}\; \backslash varphi(d)$。

若 $\gcd (n,m)=1\backslash gcd(n,m)\; =\; 1$，则 $\mathrm{\forall }{d}_1\mid n,d_2\mid m\backslash forall\; d\_1\; \backslash mid\; n,\; d\_2\; \backslash mid\; m$，有 $gcd(d_1,d_2)=1gcd(d\_1,\; d\_2)\; =\; 1$ 且 $d_1{d}_2\mid nmd\_1d\_2\; \backslash mid\; nm$，那么 $\phi (d_1)\phi (d_2)=\phi (d_1{d}_2)\backslash varphi(d\_1)\backslash varphi(d\_2)\; =\; \backslash varphi(d\_1d\_2)$。同时 $nmnm$ 的约数集为 $\{d_1{d}_2\}\backslash \{d\_1d\_2\backslash \}$。

所以：

即：

这意味着 $f(x)f(x)$ 是一个积性函数。

若 $pp$ 是质数，则：

所以若 $n={\prod }_{i=1}^m{p}_i^{c_i}n\; =\; \backslash prod\_\{i=1\}^m\; p\_i^\{c\_i\}$，则：

计算

（以下涉及一些简单的 C++ 代码和埃筛、线性筛的基础，如果不会，可以自己上网查找资料）

注：

• 埃筛：Eratosthenes 筛法的简称。
• 线性筛：又称欧拉筛。

计算单个数的欧拉函数

利用试除法和欧拉函数计算式可求 $\phi (n)\backslash varphi(n)$，时间复杂度为 $O(\sqrt{n})O(\backslash sqrt\; n)$。代码很简单，书上也有，不用另外写了。

计算 1 到 n 中所有数的欧拉函数

利用埃筛

根据计算式计算。

先来回顾埃筛板子：

void primes(int n) {
  memset(v, 0, sizeof(v));
  for (int i = 2; i <= n; ++i) {
    if (v[i]) continue;
    for (int j = i; j <= n / i; ++j)
      v[i * j] = 1;
  }
}

计算欧拉函数之前，可以先初始化 phi[i] = i。

注意到第 6 行 i 是质数，i * j 是 i 的倍数，那么 phi[i*j] = phi[i*j] / i * (i - 1)。

修改后的代码如下：

void euler(int n) {
  for (int i = 2; i <= n; ++i)
    phi[i] = i;
  for (int i = 2; i <= n; ++i) {
    if (phi[i] != i) continue; // 直接判断欧拉函数有没被改变过
    phi[i] = i - 1;
    for (int j = 2; j <= n / i; ++j) // 算欧拉函数的话一定要从 2 开始
      phi[i*j] = phi[i*j] / i * (i - 1);
  }
}

埃筛的时间复杂度为 $O(n\log n)O(n\; \backslash log\; n)$，一般不够用。

利用线性筛

印象中，某大佬说过，线性筛天生就适合计算积性函数。e.g. $\phi (n)\backslash varphi(n)$，$\mu (n)\backslash mu(n)$。

原理：性质3

设 $pp$ 为质数且 $p\mid np\; \backslash mid\; n$，则有：

等价于：

在线性筛中，第一种情况意味着 $p=v(n)p\; =\; v(n)$。这里的 $v(n)v(n)$ 指的是 $nn$ 的最小质因数。

线性筛求欧拉函数代码：

void euler(int n) {
  for (int i = 2; i <= n; ++i) {
    if (!v[i]) prime[++m] = v[i] = i, phi[i] = i - 1;
    for (int j = 1; j <= m; ++j) {
      if (prime[j] > v[i] || prime[j] > n / i) break;
      int nxt = prime[j] * i;
      v[nxt] = prime[j];
      phi[nxt] = phi[i] * (v[i]==prime[j] ? prime[j] : prime[j]-1);
    }
  }
}

例题

这篇文章写不下了，另起一篇：

https://blog.nowcoder.net/n/edc43d04c64844c08f05485e10aa75fc