初等数论程耀精.ppt

《初等数论程耀精.ppt》由会员分享，可在线阅读，更多相关《初等数论程耀精.ppt（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、初等数论程耀第1 页，本讲稿共23 页素数和合数 算术基本定理：任意正整数n 可以写成n=2a1*3a2*5a3*,其中a1,a2,a3 等为非负整数 素数的判定：判定函数 筛法求素数 miller_rabin 素性判定第2 页，本讲稿共23 页素数的判定bool Is_prime(int n)int t=(int)sqrt(n);for(int i=2;i=t;i+）if(n%i=0)return false;return true;第3 页，本讲稿共23 页筛法求素数思考：如果一个数是合数，那么它的素因子都比它小？这样说来：如果我们的当前数是 a,那么所有 a 的倍数（当然是2 倍以上啦）

2、都不会是素数，可以这样看吧？于是，我们可以一种新的素数判定方法。第4 页，本讲稿共23 页筛法求素数 方法：每次用一个素数，去筛掉所有它的倍数。举个例子：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 2829 30筛去2 的倍数，剩下3 5 7 9 11 13 15 17 19 21 23 25 27 29筛去3 的倍数，剩下5 7 11 13 17 19 25 29。注意：开头的数一定是素数？第5 页，本讲稿共23 页筛法求素数bool prime maxn;/时间复杂度O(n)?void init

3、()memset(prime,0,sizeof(prime);for(int i=4;i maxn;i+=2)primei=1;for(int i=3;i maxn;i+=2)if(!prime i)for(int j=i*i;j maxn;j+=i)prime j=1;第6 页，本讲稿共23 页miller_rabin 素性判定 miller_rabin 是一种概率型的算法，不是确定型的。但是，只要运行次数足够多，一般出错的概率是非常小的，一般10 次就好了！算法复杂度是 O(logn)3)算法的正确性是基于费马小定理。费马小定理：对于素数p 和任意整数a，有a(p-1)=1(mod p)。

4、反过来，满足a(p-1)=1(mod p),p 也几乎一定是素数。第7 页，本讲稿共23 页miller_rabin 算法分析bool miller_rabin(LL n)if(n2)return false;if(n=2)return true;if(!(n&1)return false;for(int i=1;i=12;i+)LL a=random(n-2)+1;if(witness(a,n)return false;return true;第8 页，本讲稿共23 页witness 函数 witness 函数用来搜集n 是合数的证据。bool witness(LL a,LL n)LL m=

5、n-1;int t=0;LL y;while(!(m&1)m=1;t+;/这个地方是通过一个推论来优化的，x2=1(mod n),当那个n 是合数的时候，就会出现非平凡平方根！LL x=quick_mod(a,m,n);for(int i=1;i=t;i+)y=muti(x,x,n);if(y=1&x!=1&x!=n-1)return true;x=y;if(y!=1)return true;else return false;第9 页，本讲稿共23 页快速幂取模 题目：求出mn(mod p)的值，其中 m=10000,n=100000000。分析：如果直接边乘然后边取模，直接导致 TLE！我

6、们需要一个更优的算法。我们可以发现：这其中包含着大量的重复的子问 题，利用分治的思想可以大大减小运算量。举个例子：27=24*22*21,而2t 到2(2t)只需要累乘就好了。第10 页，本讲稿共23 页快速幂取模算法分析 把指数看成一个二进制数，从低位到高位依次判断是否为1。如果是1，就要乘以2t,否则，就不需要乘上2t.其中，ak 等系数只能取0，或者1。如果取1的话，那么要乘以对应的a(2k).算法复杂度O(log n)第11 页，本讲稿共23 页快速幂取模代码分析 int quick_mod(int a,int n)int t=a,ret=1;while(n)if(n&1)ret=re

7、t*t%n;n=1;/n 右移两位，相当于除2t=t*t%n;return ret;PS：与快速幂取模类似的还有矩阵快乘，这里不展开第12 页，本讲稿共23 页最大公约数（gcd)普通算法：求出c=min(a,b),如果找到c|a&c|b,那么c减一，然后循环继续，直到 找到 c满足条件为止。欧几里得算法：int gcd(int a,int b)return b?gcd(b,a%b):a;第13 页，本讲稿共23 页欧几里得算法的证明 证明：令m 是a,b 的公约数，而a 可以表示为a=n*b+r,其中r=0&rb那么r=a-n*b,可以知道r 能够被 m 整除。同理：如果m 是r 和 b 的

8、公约数。那么，a=n*b+r,所以，m 也能够整除a.由上面的两条可知：a,b 和b,r 具有相同的公约数，故欧几里得算法成立。第14 页，本讲稿共23 页扩展欧几里得算法 应用：常用来求解形如a*x+b*y=gcd(a,b)的二元一次不定方程代码如下：void extended_gcd(int a,int b,int&x,int&y)if(b=0)x=1;y=0;return;extended_gcd(b,a%b,x,y);int temp=x;x=y;y=temp-a/b*y;第15 页，本讲稿共23 页扩展欧几里得算法分析证明：令d=gcd(a,b);a*x+b*y=d.b*x1+(a%

9、b)*y1=d.那么我们可以由x1,y1 的值反推出x,y 的值。把两式联立，消去d,并且用a-a/b*b 来替换a%b;然后可以令x=y1,推出y=x1-a/b*y1;第16 页，本讲稿共23 页扩展欧几里得算法的注意事项形如a*x+b*y=c 的方程,如果gcd(a,b)能够整除c,那么此方程有解，否则无解。并且它的特解形式为x=c/gcd(a,b)*x0,y=c/gcd(a,b)*y0(其中 x0,y0 是用扩展欧几里得算法求出的解）通解的形式：x=x0-b/d*ty=y0+a/d*t其中：t 是整数。第17 页，本讲稿共23 页a 关于模n 的乘法逆元 什么是乘法逆元？如果a*b=1(

10、mod n),那么b 就是a 关于模n 的乘法逆元，此时，也可以称作a 与b 互为乘法逆元。第18 页，本讲稿共23 页乘法逆元的应用题目：输出C(n,m)%p,其中p 是一个素数。n10000.思考：如果使用边除边模的方法，也会有出现大数，导致精度溢出。(a/b)%p!=(a%p)/(b%p)%p;解决方案：除以一个数并取模，就相当于是乘以它的逆元然后再取模。第19 页，本讲稿共23 页如何求解乘法逆元上式等价a*x+b*n=1 的解，所以可以应用扩展欧几里得算法来求出x的值。为了保证x是正整数，通常需要加上：x=(x%n+n)%n；int inv(int a,int n)int x,y;e

11、xtended_gcd(a,n,x,y);x=(x%n+n)%n;return x;第20 页，本讲稿共23 页扩展阅读AekdyCoin 的博客：http:/神牛被称为数学帝，里面收录了好多数论方面的知识，其中最经典的就是各种大数取模.笨小孩的博客：http:/页，本讲稿共23 页最后一页 qinz 大牛的博客：http:/qinz.maybe.im/最值得一看的就是qinz 大牛的ACM 装逼录，我已经看了不知道多少遍了，但是，总是感觉百看不厌。强烈推荐大家看看！最后的话：可能每个acmer 都会怀揣着各自不同的目标。但是，当你沉浸在其中的时候，你发现自己真的爱上了它。算法这个东西真的很奇妙，真的会让你受益一生。第22 页，本讲稿共23 页大家多多A 题!天天进步!thanck you for listening第23 页，本讲稿共23 页