欧拉函数相关

作者: shad0w_walker(admin) 分类: 谜数学 发布时间: 2016-07-21 11:11 ė 6 没有评论

说是数论只会gcd的我其实真的遇到,连gcd都不会,怎么办呢!那就看欧拉函数压压惊吧。

 

一、定义:

一个正整数的欧拉函数定义为小于它且与它互质的正整数的个数。(φ(1)=1)

 

二、性质:

1、对于质数p,φ(p)=p-1

2、\(\varphi (x)=x(1-\frac{1}{p_{1}})(1-\frac{1}{p_{2}})(1-\frac{1}{p_{3}})……(1-\frac{1}{p_{n}})\),其中p1,p2,p3,…,pn为x的质因子

3、若\(n=p^{k}\),则\(\varphi (n)=p^{k}-p^{k-1}=(p-1)p^{k-1}\)

4、当n为奇数时,φ(2n)=φ(n)

5、欧拉函数是积性函数,若p,q互质,则φ(pq)=φ(p)φ(q)

6、推广:设p为素数且p|n,若p^2|n,则\(\varphi (n)=\varphi (\frac{n}{p})*p\),否则\(\varphi (n)=\varphi (\frac{n}{p})*(p-1)\)

 

三、应用

1、求单个数的欧拉函数值

求单个数n的欧拉函数值思路就是先将n分解质因数然后利用性质3和5相乘计算

复杂度\(O(\log{N})\)

 

2、求1-n的欧拉函数表

与素数筛类似,一边筛素数一边计算欧拉函数值,具体的实现利用了上述性质6

复杂度\(O(N)\)

 

3、指数降幂公式

\(A^{n}\mod{p}=A^{n\mod{\varphi (p)+\varphi (p)}}\mod{p}\)

丢个公式就跑,真tm刺激

本文出自shad0w_walker,转载时请注明出处及相应链接。

本文永久链接: https://www.sdwalker.com/archives/477.html

发表评论

电子邮件地址不会被公开。 必填项已用*标注

返回顶部