欧拉函数&线性筛

发表于 更新于

欧拉函数&线性筛

1. 定义

$\varphi(n)$ 表示所有与$n$互质的正整数$i$的个数，其中$i <= n$.

2. 欧拉定理

欧拉定理是指对于任意互质的正整数$a$ 和 $n$，有:

$$
a^{\varphi(n)} \equiv 1\pmod{n}
$$

3. 证明

记小于$n$且与$n$互质的正整数集合$R$为：

$$
R = { r_1,r_2,r_3,……,r_{\varphi(n)}}
$$

再令集合S为：

$$
S = {a\times r_1 % n,a \times r_2 % n,……,a\times r_{\varphi(n)}%n}
$$

现在我们先证明$S$中的元素两两互不相同。

反证法：假设存在两个整数$i$ 和$j$（方便起见，令$i < j$）使得$a \times r_i % n = a \times r_j % n$,则：

$$
a \times r_i \equiv a \times r_j \pmod{n}
$$

又因为$a$与$n$互质，所以$r_i = r_j$,而$i < j$，即 $r_i \neq r_j$，矛盾，所以$S$中元素两两互不相同。

又因为$a$ 与 $n$互质，$r_i$与 n互质，所以易得$a * r_i % n$与 $n$ 互质，即$S$中的元素都与 $n$ 互质。

所以可以得到 $R = S$.

所以 ：

$$
\prod_{i = 1}^{\varphi(n)}{r_i} = \prod_{i = 1}^{\varphi(n)}{a \times r_i%n}
$$

$$
\prod_{i = 1}^{\varphi(n)}{r_i} \equiv \prod_{i = 1}^{\varphi(n)}{r_i \times a} \pmod{n}
$$

$$
\prod_{i = 1}^{\varphi(n)}{r_i} \equiv a^{\varphi(n)} \times \prod_{i = 1}^{\varphi(n)}{r_i} \pmod{n}
$$

又因为$\prod_{i = 1}^{\varphi(n)}{r_i} $ 与 n 互质，

所以：
$$
a^{\varphi(n)} \equiv 1 \pmod{n}
$$

4.线性筛

先上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;

const int maxn = 1e6 + 5;
int prime[maxn],px,l,r,n;
bool b[maxn];

int main() {
	scanf("%d",&n);
	for (int i=2; i<=n; i++) {
		if (!b[i]) 
			prime[++px] = i;
		for (int j=1; j<=px && i * prime[j] <= n; j++) {
			b[prime[j] * i] = 1;
			if (i % prime[j] == 0)
				break;
		}
	}
	for (int i=1; i<=px; i++)
		printf("%d\n",prime[i]);
	return 0;
}

算法的正确性证明中，其实我们要证明的就是两点：

  • 每一个合数都会被筛掉。
  • 每一个合数只能被筛一遍（以保证时间复杂度$O(n)$)

对于第一点，证明如下：

设这个合数为$v$,则 $v = p_1 p_2 …… p_k(p_i<=p_{i+1})$，$p$ 为 $v$的质因数。

可以发现，当$i = p_2 \cdot p_3 \cdot …… \cdot p_k$, $prime[j] = p_1$时，$i$与所有小于$p_1$的质数互质，所以中途不会被break掉，所以此时$v$可以被筛掉。

对于第二点，证明如下：

在第一点中，我们是证明了v会在$i = p_2 \times p_3 \times …… \times p_k$, $prime[j] = p_1$时被筛掉，那么现在就是要证明除了这种情况外，v不会被筛掉。

设当$i = p_1 \times p_2 \times … \times p_{m - 1} \times p_{m + 1} \times … \times p_k$ $(p_i <= p_{i + 1})$ 时

$prime[j] = p_m(p_m \neq p_1)$时 v 被筛掉.

可以发现 $p_1 | i$,所以当$prime[j] = p_1$时就会被break掉，所以v不会在此时被筛掉。

由此，我们可以证明，算法的正确性和时间复杂度的正确性。

5.求欧拉函数

首先，欧拉函数是一个积性函数。

积性函数的定义是：函数$f(x)$,若满足$f(m \times n) = f(m) \times f(n) (gcd(n,m) = 1)$,那么$f(x)$就是一个积性函数。

欧拉函数是一个积性函数。

设$n = p_1^{m_1} \times p_2^{m_2} \times p_3^{m_3} \times …… \times p_k^{m_k} $,$p_i\in P$，则有：

$$
\varphi(n) = \varphi(p_1^{m_1}) \times \varphi(p_2^{m_2}) \times …… \times \varphi(p_k^{m_k})
$$

对于$\varphi(p^k),p_i \in P$，易得$\varphi(p^k) = p^k - p^{k - 1} = p^k \times (1 - \frac{1}{p})$

所以有：

$$
\varphi(n) = p_1^{m_1} \times p_2^{m_2} \times p_3^{m_3} \times …… \times p_k^{m_k} \times (1 - \frac{1}{p_1}) \times (1 - \frac{1}{p_2}) \times …… \times (1 - \frac{1}{p_k}) \= n \times (1 - \frac{1}{p1}) \times (1 - \frac{1}{p2}) \times …… \times (1 - \frac{1}{p_k}))
$$

特别的，当$n \in P$时，$\varphi(n) = n - 1$.

理解了上面这些，可以上代码了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
#include<cstdio>
using namespace std;

const int maxn = 1e6 + 5;
int n,phi[maxn],prime[maxn],px;
bool b[maxn];

int main() {
	scanf("%d",&n);
	for (int i=2; i<=n; i++) {
		if (!b[i]) {
			prime[++px] = i;
			phi[i] = i - 1;
		}
		for (int j=1; j<=px && prime[j] * i <= n; j++) {
			b[i * prime[j]] = 1;
			if (i % prime[j] == 0) {
				phi[i * prime[j]] = phi[i] * prime[j];
				break;
			}
			phi[i * prime[j]] = phi[i] * phi[prime[j]];
		}
	}
	phi[1] = 1;
	for (int i=1; i<=n; i++)
		printf("%d\n",phi[i]);
	return 0;
}

可以看到，这个代码是由线性筛变过来的。

当$i \in P$时，毫无疑问$\varphi(i) = i - 1$.

当$i \notin P$时，分以下两种情况讨论：

  • 若$i % prime[j] \neq 0$，因为$prime[j] \in P$,所以$gcd(i,prime[j])) = 1$。因此根据积性函数的定义，有：

$$
\varphi(i \times prime[j]) = \varphi(i) \times \varphi(prime[j])
$$

  • 若$i % prime[j] = 0$，因为$prime[j] \in P$,所以$prime[j]$必定为 i 的一个质因数，所以$prime[j]$必定是$p_1,p_2,p_3,……,p_k$中的一个，因此得到：
    $$
    \varphi(i \times prime[j]) = i \times prime[j] \times (1 - \frac{1}{p1}) \times (1 - \frac{1}{p2}) \times …… \times (1 - \frac{1}{p_k})) = \varphi(i) \times prime[j]
    $$

最后和线性筛一样，可以证明欧拉函数求法时间复杂度也是线性的。

特别的，$\varphi(1) = 1$.

6.一些神奇定理

  • $\sum_{d|n}\varphi(d) = n$

  • $\forall n > 1,1-n$中与n互质的数的和为$n \times \varphi(n) / 2$

  • $若gcd(a,n) = 1$ $ \forall 正整数b$ $a^b \equiv a^{b \ mod \ \varphi(n)}(mod\ n)$

  • 若$a$,$n$互质，则满足$a^x \equiv 1 (mod \ n)$的最小正整数$x_0$是$\varphi(n)$的约数。