技术类数论讲座

1、1 ACM/ICPC数论讲座数论讲座王侯将相宁有种乎？大牛神牛宁有种乎？王侯将相宁有种乎？大牛神牛宁有种乎？ 何以解忧？唯有何以解忧？唯有AC！ 向百度学习，向谷歌学习！向百度学习，向谷歌学习！3主要内容主要内容1. 素数及筛选法求素数素数及筛选法求素数 2. 算术基本定理（整数的唯一素因子分解）算术基本定理（整数的唯一素因子分解）3. 欧几里德算法欧几里德算法4. 扩展的欧几里德算法扩展的欧几里德算法(ax+by=gcd(a,b)5. 线性同余方程线性同余方程6. 中国剩余定理中国剩余定理7. 费马小定理费马小定理8. 欧拉函数与欧拉公式欧拉函数与欧拉公式9. 快速幂取模快速幂取模4一一.素

2、数及筛选法求素数素数及筛选法求素数1. 实现见模板实现见模板P272. 模板模板“高效求小范围素数高效求小范围素数”中：中： k=i*2，应改为：，应改为：k=i*i3. 问题：问题： hdoj1164：Eddys research I poj3048：Max Factor 5二、算术基本定理二、算术基本定理【定理】正整数【定理】正整数n(n2)可以唯一分解成素数乘积，可以唯一分解成素数乘积，即：即：n = 。1. 详细证明见：什么是数学。详细证明见：什么是数学。2. 此定理非常重要，它可以解决数论中很多重要此定理非常重要，它可以解决数论中很多重要 问题。问题。3. 注意：如果注意：如果p是整

3、数是整数n的素因子，则的素因子，则p一定出现在一定出现在 p1 p2 ps 中。中。4. 对对n进行素因子分解可以改造进行素因子分解可以改造P27之之“单独求欧拉单独求欧拉 函数函数”。1212.srrrsp pp6三、欧几里德算法三、欧几里德算法1. gcd(a, b) = gcd(b, a%b)2. 实现见模板实现见模板P277四、扩展的欧几里德算法四、扩展的欧几里德算法1. 目的：求目的：求ax + by = gcd(a, b)2. 如果如果b=0，则，则ax + 0y = gcd(a, 0) = a，得，得:x=1, y=0 .3. 显然在欧几里得算法的最后会出现形式显然在欧几里得算法

4、的最后会出现形式gcd(a, 0)。4. 结合结合2、3，使用逆推便可解得，使用逆推便可解得x和和y。5. ax + by = gcd(a, b) = gcd(b, a%b) = b*x + a%b *y = b*x + (a a/b *b) *y = a*y + b(x a/b *y )6. 实现见模板实现见模板P278五、线性同余方程五、线性同余方程1. 目的：解方程目的：解方程 ax c (mod m)2. 补充：补充： a1 b1 (mod m) 且且 a2 b2 (mod m) ，则，则 a1 a2 b1 b2 (mod m)， a1 a2 b1 b2 (mod m)。 如果如果 g

5、cd(c, m) = 1, 则由则由ac bc(mod m) ，得：，得： a b (mod m)。9五、线性同余方程（续）五、线性同余方程（续）3. ax c (mod m)， 则：则： ax c = my, 所以：所以：ax my = c. 又：又： ax my = gcd(a, m) = g，解是存在的。，解是存在的。 显然：显然：g | c 则上述方程有解，否则无解。设方程则上述方程有解，否则无解。设方程 ax my = gcd(a, m) = g的解为的解为x=u0, 则原方程的解则原方程的解为：为：x0 = cu0 / g ，不同余解集为：，不同余解集为： x x0 + k* m/

6、g (mod m) , k=0, 1, 2, , g-14. 实现见模板实现见模板P2710五、线性同余方程（续）五、线性同余方程（续）5. 问题：问题： poj1061：青蛙的约会：青蛙的约会 poj2115： C Looooops 11六、中国剩余定理六、中国剩余定理1. 伟大的孙子，孙子算经（伟大的孙子，孙子算经（4世纪、晋朝）世纪、晋朝）2. 明朝算法统宗明朝算法统宗 ： 三人同行七十稀，三人同行七十稀，五树梅花廿一枝，五树梅花廿一枝，七子团圆正半月，七子团圆正半月，除百零五便得知。除百零五便得知。12六、中国剩余定理（续）六、中国剩余定理（续）3. 中国剩余定理：中国剩余定理： 设设

7、m1, m2, , mk两两互素，则下面同余方程组：两两互素，则下面同余方程组： x a1 (mod m1) x a2 (mod m2) x ak (mod mk)在在0 x M = m1m2mk内有唯一解。内有唯一解。13六、中国剩余定理（续）六、中国剩余定理（续） 记记 Mi = M/mi (1 i k)， 因为因为gcd(Mi, mi) = 1, 故有故有整数整数xi、yi满足：满足：Mi xi + miyi = 1, 如果记如果记ei = Mixi ,则有：则有： 0 (mod mj), j i 1 (mod mj), j = i很明显：很明显：e1a1 + e2a2 + + ekak

8、 就是方程的一个解。就是方程的一个解。4. 实现见模板实现见模板P27ei 14六、中国剩余定理（续）六、中国剩余定理（续） 5. 问题问题 poj1006：Biorhythms 15七、费马小定理七、费马小定理1.【定理】设【定理】设p是素数，是素数，a是任意整数且是任意整数且a 0(mod p)，则：则： ap-1 1 (mod p)。2. a 0(mod p) 在这里等价于在这里等价于 gcd( a, p) = 1 3. 费马小定理是欧拉公式的特殊形式费马小定理是欧拉公式的特殊形式16八、欧拉函数与欧拉公式八、欧拉函数与欧拉公式1. 欧拉函数欧拉函数 (m) = |a | 1 a m,

9、gcd(a, m)=1|2. 如果如果p是素数，则是素数，则(p) = p 1 = p(1-1/p)3. 欧拉公式：如果欧拉公式：如果gcd(a, m) = 1, 则：则： a (m) 1 (mod m)4. 设设p是素数，是素数， (pk) = pk pk-1 = pk(1-1/p)5. 如果如果gcd(m, n) = 1, 则则(mn) = (m) (n) 17八、欧拉函数与欧拉公式（续）八、欧拉函数与欧拉公式（续）6. m = ，则：，则： (m) = (p1r1) (p2r2) (psrs) =p1r1(1-1/p1) p2r2(1-1/p2) psrs(1-1/ps) =p1r1 p

10、2r2psrs(1-1/p1) (1-1/p2) (1-1/ps) = m ( 1- 1/p1) ( 1- 1/p2)( 1- 1/ps)7. 欧拉函数的实现见模板欧拉函数的实现见模板P271212.srrrsp pp18八、欧拉函数与欧拉公式（续）八、欧拉函数与欧拉公式（续）8. 问题：问题： poj2407： Relatives hdoj1286：找新朋友：找新朋友 poj3090：Visible Lattice Points poj2478: Farey Sequence 19九、快速幂取模九、快速幂取模1. 目的：求目的：求 ab mod m2. 作用作用RSA加密加密3. 方法：方法