欧拉函数&线性筛

发表于 更新于

欧拉函数&线性筛

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} \]

又因为$_{i = 1}^{(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} p_2^{m_2} p_3^{m_3} …… p_k^{m_k} \(,\)p_iP$，则有：

\[ \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\) $ 正整数b$ \(a^b \equiv a^{b \ mod \ \varphi(n)}(mod\ n)\)

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