ACM的数学基础
懒得整理了,请勿往下看。
(一)欧拉函数
设n为正整数,以φ(n)表示不超过n且与n互素的正整数的个数,称为n的欧拉函数值,这里函数φ:N→N,n→φ(n)称为欧拉函数。有如下一些性质:
(1)欧拉函数是积性函数——若m,n互质,φ(mn)=φ(m)φ(n)。
(2)特殊性质:当n为奇数时,φ(2n)=φ(n), 证明与上述类似。欧拉函数值总是为偶数(除了特殊情况)。
(3)若n为质数则φ(n)=n-1。
(4)若n=pk,φ(n) = pk - p(k-1) = (p-1)*p(k-1),因为除了p的倍数外,其他数都跟n互质。
(5)φ函数值的通式:φ(x)=x*(1-1/p1)*(1-1/p2)*(1-1/p3)*(1-1/p4)*…..*(1-1/pn),其中p1, p2……pn为x的所有质因数,且x>=2。特殊情况 φ(1)=1。 (注意:每种质因数只需要一个。
比如12=2*2*3那么φ(12)= 12*(1-1/2)*(1-1/3)=4,因为1,5,7,11均和12互质。比如φ(8)=4,因为1,3,5,7均和8互质。
(二)欧拉定理
若n与a互质,且皆为正整数,则。
(三)乘法逆元
定义:满足a*k≡1 (mod p)的k值就是a关于p的乘法逆元。
(1)为什么要有乘法逆元呢?
答:当我们要求(a/b) mod p的值,且a很大,无法直接求得a/b的值时,我们就要用到乘法逆元。
定理:a存在模p的乘法逆元的充要条件是gcd(a,p) = 1
(2)如何求解 (a/b) mod p 的结果?
答:我们可以通过求b关于p的乘法逆元k,将a乘上k再模p( 即ans=(a*k)%p,这样就比较好算了 )。其结果与 (a/b) % p 等价。
(3)如何证明?
证明:
根据b*k≡1 (mod p)有b*k=p*x+1,那么k=(p*x+1)/b。
把k代入(a*k) mod p,得:
(a*(p*x+1)/b) mod p
=((a*p*x)/b+a/b) mod p
=[((a*p*x)/b) mod p +(a/b)] mod p
=[(p*(a*x)/b) mod p +(a/b)] mod p
//注:p*[(a*x)/b] mod p=0,因为既然要取模,a/b的结果肯定是为正整数。
所以原式等于:(a/b) mod p
证毕!
补:还有一条公式也是用于求模用的:
(ans表示我们要求的结果,且无需考虑所有数字的特殊性)
最新文章
- 项目中常用的linux命令
- css3动画之图片旋转
- 用matlab实现同一个序列重复N倍
- support HTML5 in IE8
- 【mongodb系统学习之十二】mongodb修改数据(一)
- linux云计算集群架构学习笔记:rhel7基本命令操作
- Linux VIM python 自动补全插件:pydiction
- qt model/view 架构基础介绍之QTableWidget
- WPF中图形表示语法详解(Path之Data属性语法)
- IIS的安装
- (23)unity4.6学习Ugui中国文档-------非官方Demo1
- <;!特别的一天>;
- input autocomplete属性设计输入框自动联想(php实现)
- python线程——创建和启动
- Unable to cast object of type &#39;System.Int32&#39; to type &#39;System.Array&#39;.
- Oracle触发器(trigger):一般用法
- Java设计模式之【单例模式】
- 构建高性能数据库缓存之redis主从复制
- python之字符串【str】
- poj2462