数论 —— 欧拉函数
数论算法,欧拉函数公式推导 + 代码
欧拉函数
定义一个函数 e u l e r ( N ) euler(N) euler(N) 为 [ 1 , N ] [1,N] [1,N] 中与 N N N 互质的数的个数,这个函数称为 欧拉函数
公式
e u l e r ( N ) = N ( 1 − 1 p 1 ) ( 1 − 1 p 2 ) . . . . ( 1 − 1 p k ) euler(N) = N(1-\dfrac{1}{p_1})(1-\dfrac{1}{p_2})....(1- \dfrac{1}{p_k}) euler(N)=N(1−p11)(1−p21)....(1−pk1)
p i p_i pi 为 N N N 的所有质因数
性质
- 欧拉函数的值与 N N N 的质因子的指数无关
推导
- 基于容斥原理推导
思路
欧拉函数求的是 [ 1 , N ] [1,N] [1,N] 中与 N N N 互质的数的个数,我们反过来看 [ 1 , N ] [1,N] [1,N] 中有几个数与 N N N 不互质;与 N N N 不互质,说明与 N N N 有一些公共质因数,所以我们将 N N N 的所有质因数的倍数的个数减去,剩下的就是互质数的个数
假设 N N N 的质因数为 { p 1 , p 2 , p 3 . . . . , p k } \{ p_1,p_2,p_3....,p_k\} {p1,p2,p3....,pk}, 则
p 1 p_1 p1 在 [ 1 , N ] [1,N] [1,N] 内的倍数的个数为 N p 1 \dfrac{N}{p_1} p1N
p 2 p_2 p2 在 [ 1 , N ] [1,N] [1,N] 内的倍数的个数为 N p 2 \dfrac{N}{p_2} p2N
…
p k p_k pk 在 [ 1 , N ] [1,N] [1,N] 内的倍数的个数为 N p k \dfrac{N}{p_k} pkN
所以我们将他们减去,即 N − N p 1 − N p 2 . . . . . − N p k N - \dfrac{N}{p_1}-\dfrac{N}{p_2}.....-\dfrac{N}{p_k} N−p1N−p2N.....−pkN
但是,有些数会是多个质因数的公倍数,他们被重复减了,所以要把他们加回去
p 1 p 2 p_1p_2 p1p2 在 [ 1 , N ] [1,N] [1,N] 内的倍数的个数为 N p 1 p 2 \dfrac{N}{p_1p_2} p1p2N
p 1 p 3 p_1p_3 p1p3 在 [ 1 , N ] [1,N] [1,N] 内的倍数的个数为 N p 1 p 3 \dfrac{N}{p_1p_3} p1p3N
p 2 p 3 p_2p_3 p2p3 在 [ 1 , N ] [1,N] [1,N] 内的倍数的个数为 N p 2 p 3 \dfrac{N}{p_2p_3} p2p3N
…
所以将他们加回去,即 N − N p 1 − N p 2 . . . . . − N p k + N p 1 p 2 + N p 1 p 3 + N p 2 p 3 . . . . N - \dfrac{N}{p_1}-\dfrac{N}{p_2}.....-\dfrac{N}{p_k}+\dfrac{N}{p_1p_2}+\dfrac{N}{p_1p_3}+\dfrac{N}{p_2p_3}.... N−p1N−p2N.....−pkN+p1p2N+p1p3N+p2p3N....
但是但是,我们又发现,如果一个数同时是 p 1 p 2 p 3 p_1p_2p_3 p1p2p3 的公倍数,那么经过最上面被减了三次,然后又被加了三次,相当于没减,所以我们还要将他减掉
p 1 p 2 p 3 p_1p_2p_3 p1p2p3 在 [ 1 , N ] [1,N] [1,N] 内的倍数的个数为 N p 1 p 2 p 3 \dfrac{N}{p_1p_2p_3} p1p2p3N,则
KaTeX parse error: \tag works only in display equations
而这条式子化简之后就是欧拉函数公式
e
u
l
e
r
(
N
)
=
N
(
1
−
1
p
1
)
(
1
−
1
p
2
)
(
1
−
1
p
3
)
.
.
.
(
1
−
1
p
k
)
euler(N) = N(1-\dfrac{1}{p_1})(1-\dfrac{1}{p_2})(1-\dfrac{1}{p_3})...(1-\dfrac{1}{p_k})
euler(N)=N(1−p11)(1−p21)(1−p31)...(1−pk1)
得证
代码
定义法
- 思路:一边分解质因数,一边求欧拉函数
- 但是一次只能求一个数的欧拉函数
int get_euler(int n)
{
int euler = n;
for (int i = 2; i <= n / i; i++)
{
if (n % i == 0)
{
euler = euler / i * (i - 1) //euler = euler * (1 - 1 / i);
while (n % i == 0) n /= i;
}
}
if (n > 1) euler = euler / n * (n - 1);
return euler;
}
线性筛法
- 在线性筛筛质数的过程中,求出每个数的欧拉函数
- 可以一次筛的过程中一次性将 [ 1 , N ] [1,N] [1,N] 中所有数的欧拉函数都求出来,但是思路需要推导
int primes[N], cnt = 0;
int euler[N];
bool st[N];
int get_euler(int n)
{
euler[1] = 1; // 1的欧拉函数值是1
// 线性筛模板 + 过程中求欧拉函数
for (int i = 2; i <= n; i++)
{
if (!st[i])
{
primes[cnt ++] = i;
euler[i] = i - 1; // (1)式
}
for (int j = 0; primes[j] <= n / i; j++)
{
st[i *primes[j]] = true;
if (i % primes[j] == 0)
{
euler[i * primes[j]] = euler[i] * primes[j]; //(2)式
break;
}
euler[i * primes[j]] = euler[i] * (primes[j] - 1);//(3)式
}
}
// 最后,euler数组中存的就是 1 ~ n 每个数的欧拉函数值
}
( 1 ) ( 2 ) ( 3 ) (1)(2)(3) (1)(2)(3) 式的推导
( 1 ) (1) (1) 式:
- 当 i i i 是质数的时候,质数的因数只有 1 1 1 和他本身,所以 i i i 会与小于它的所有数互质,即 i i i 与 [ 1 , i − 1 ] [1,i-1] [1,i−1] 中所有数互质。即:当 i i i 是质数的时, e u l e r ( i ) = i − 1 euler(i) = i - 1 euler(i)=i−1
( 2 ) ( 3 ) (2)(3) (2)(3) 式:
-
当一个数是合数的时候,它在第二个for循环中被筛掉。
-
但合数的欧拉函数会出现两种情况:
-
当 i i i 能被 p r i m e s [ j ] primes[j] primes[j] 整除时
-
说明 p r i m e s [ j ] primes[j] primes[j] 是 i i i 的一个质因子(且是最小质因子),则 i i i 的所有质因数为 { p 1 , p 2 , . . . p k , p j } \{ p_1,p_2,...p_k,p_j\} {p1,p2,...pk,pj}(我们将 p r i m e s [ j ] primes[j] primes[j] 记作 p j p_j pj)。而合数 i × p r i m e s [ j ] i\times primes[j] i×primes[j] (我们将 p r i m e s [ j ] primes[j] primes[j] 记作 p j p_j pj) 的所有质因数也是 { p 1 , p 2 , . . . p k , p j } \{ p_1,p_2,...p_k,p_j\} {p1,p2,...pk,pj},则
-
e u l e r ( i × p j ) = i p j ( 1 − 1 p 1 ) ( 1 − 1 p 2 ) . . . ( 1 − 1 p j ) e u l e r ( i ) = i ( 1 − 1 p 1 ) ( 1 − 1 p 2 ) . . . ( 1 − 1 p j ) euler(i\times p_j) =ip_j(1-\dfrac{1}{p_1})(1-\dfrac{1}{p_2})...(1-\dfrac{1}{p_j})\\ euler(i)=i(1-\dfrac{1}{p_1})(1-\dfrac{1}{p_2})...(1-\dfrac{1}{p_j}) euler(i×pj)=ipj(1−p11)(1−p21)...(1−pj1)euler(i)=i(1−p11)(1−p21)...(1−pj1)
则:
-
e u l e r ( i × p j ) = e u l e r ( i ) × p j euler(i\times p_j) = euler(i)\times p_j euler(i×pj)=euler(i)×pj
-
而就是 ( 2 ) (2) (2) 式
-
-
当 i i i 不能被 p r i m e s [ j ] primes[j] primes[j] 整除时
-
则 i i i 的质因数没有 p j p_j pj,是 { p 1 , p 2 . . . p k } \{p_1,p_2...p_k \} {p1,p2...pk},则此时
-
e u l e r ( i ) = i ( 1 − 1 p 1 ) ( 1 − 1 p 2 ) . . . ( 1 − 1 p k ) euler(i) = i(1-\dfrac{1}{p_1})(1-\dfrac{1}{p_2})...(1-\dfrac{1}{p_k}) euler(i)=i(1−p11)(1−p21)...(1−pk1)
-
而 i × p j i\times p_j i×pj 的质因数为 { p 1 , p 2 . . . p k , p j } \{p_1,p_2...p_k,p_j \} {p1,p2...pk,pj},则
-
e u l e r ( i × p j ) = i p j ( 1 − 1 p 1 ) ( 1 − 1 p 2 ) . . . ( 1 − 1 p k ) ( 1 − 1 p j ) euler(i \times p_j) = ip_j(1-\dfrac{1}{p_1})(1-\dfrac{1}{p_2})...(1-\dfrac{1}{p_k})(1-\dfrac{1}{p_j}) euler(i×pj)=ipj(1−p11)(1−p21)...(1−pk1)(1−pj1)
式子整理后
-
e u l e r ( i × p j ) = i ( 1 − 1 p 1 ) ( 1 − 1 p 2 ) . . . ( 1 − 1 p k ) ( p j − 1 ) euler(i \times p_j) = i(1-\dfrac{1}{p_1})(1-\dfrac{1}{p_2})...(1-\dfrac{1}{p_k})(p_j-1) euler(i×pj)=i(1−p11)(1−p21)...(1−pk1)(pj−1)
-
将两式子结合为
e u l e r ( i × p j ) = e u l e r ( i ) × ( p j − 1 ) euler(i \times p_j) =euler(i)\times (p_j - 1) euler(i×pj)=euler(i)×(pj−1) -
即为 ( 3 ) (3) (3) 式
-
-
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)