《初等数论-程耀.ppt》由会员分享,可在线阅读,更多相关《初等数论-程耀.ppt(23页珍藏版)》请在三一文库上搜索。
1、XDU_ACM-初等数论,程耀,素数和合数,算术基本定理:任意正整数n可以写成n=2a1*3a2*5a3*,其中a1,a2,a3等为非负整数 素数的判定: 判定函数 筛法求素数 miller_rabin素性判定,素数的判定,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; ,筛法求素数,思考:如果一个数是合数,那么它的素因子 都比它小? 这样说来:如果我们的当前数是 a ,那么所有 a的倍数(当然是2倍以上啦)都不会是素
2、数 ,可以这样看吧? 于是,我们可以一种新的素数判定方法。,筛法求素数,方法:每次用一个素数,去筛掉所有它的倍数。 举个例子: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 28 29 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 。 注意:开头的数一定是素数?,筛法求素数,bool prime maxn ;/时间复杂度O(n)? void init ( ) memset(prime, 0
3、 ,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; ,miller_rabin素性判定,miller_rabin是一种概率型的算法,不是确定型的。但是,只要运行次数足够多,一般出错的概率是非常小的,一般10次就好了! 算法复杂度是 O(logn)3) 算法的正确性是基于费马小定理。 费马小定理:对于素数p和任意整数a,有 a(p-1)=1(mod p)。反过
4、来,满足a(p-1)= 1(mod p),p也几乎一定是素数。,miller_rabin算法分析,bool miller_rabin(LL n) if(n2) return false; if(n=2) return true; if(!(n ,witness函数,witness函数用来搜集n是合数的证据。 bool witness(LL a,LL n) LL m=n-1; int t=0; LL y; while(!(m ,快速幂取模,题目:求出mn ( mod p) 的值,其中 m=10000, n=100000000。 分析:如果直接边乘然后边取模,直接导致 TLE!我们需要一个更优的算
5、法。 我们可以发现:这其中包含着大量的重复的子问 题,利用分治的思想可以大大减小运算量。 举个例子:27 = 24 * 22 * 21,而2t到2(2t)只需要累乘就好了。,快速幂取模算法分析,把指数看成一个二进制数,从低位到高位依次判断是否为1。如果是1,就要乘以2t,否则,就不需要乘上2t. 其中,ak等系数只能取0,或者1。如果取1的话,那么要乘以对应的a(2k). 算法复杂度O(log n),快速幂取模代码分析,int quick_mod ( int a , int n ) int t =a , ret =1; while( n ) if( n PS:与快速幂取模类似的还有矩阵快乘,这
6、里不展开,最大公约数(gcd),普通算法:求出c=min( a , b),如果找到c|a ,欧几里得算法的证明,证明:令m是a , b 的公约数,而a可以表示为 a = n*b + r,其中r=0 & rb 那么r = a - n*b,可以知道r 能够被 m 整除。 同理:如果m是r 和 b 的公约数。那么, a=n*b +r,所以,m也能够整除a. 由上面的两条可知:a,b和b,r具有相同的公约数,故欧几里得算法成立。,扩展欧几里得算法,应用:常用来求解形如a*x+b*y=gcd(a,b)的二元一次不定方程 代码如下: void extended_gcd( int a, int b, int
7、 ,扩展欧几里得算法分析,证明:令d = gcd( a , b); a*x + b*y=d . b*x1+(a%b)*y1=d 那么我们可以由x1,y1的值反推出x,y的值。 把两式联立,消去d,并且用a-a/b*b来 替换a%b;然后可以令x=y1,推出y=x1-a/b*y1;,扩展欧几里得算法的注意事项,形如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*t y= y0 + a/
8、d*t 其中:t是整数。,a关于模n的乘法逆元,什么是乘法逆元? 如果a*b=1(mod n),那么b就是a 关于模n的乘法逆元,此时,也可以称作a与b互为乘法逆元。,乘法逆元的应用,题目:输出C(n,m)%p,其中p是一个素数。n10000. 思考:如果使用边除边模的方法,也会有出现大数,导致精度溢出。 (a/b)%p != (a%p)/(b%p)%p; 解决方案:除以一个数并取模,就相当于是乘以它的逆元然后再取模。,如何求解乘法逆元,上式等价a*x+b*n=1的解,所以可以应用扩展欧几里得算法来求出x的值。 为了保证x是正整数,通常需要加上: x=(x%n+n)%n; int inv(in
9、t a , int n) int x,y; extended_gcd(a,n,x,y); x=(x%n+n)%n; return x; ,扩展阅读,AekdyCoin的博客:http:/ AC神牛被称为数学帝,里面收录了好多数论方面的知识,其中最经典的就是各种大数取模. 笨小孩的博客: http:/ 这个博客收录了各种数论题的分类,有志于做数论专题的同学可以参考。,最后一页,qinz大牛的博客:http:/qinz.maybe.im/ 最值得一看的就是qinz大牛的ACM装逼录, 我已经看了不知道多少遍了,但是,总是感觉百看不厌。强烈推荐大家看看! 最后的话:可能每个acmer都会怀揣着各自不同的目标。但是,当你沉浸在其中的时候,你发现自己真的爱上了它。算法这个东西真的很奇妙,真的会让你受益一生。,大家多多A题! 天天进步!,thanck you for listening,
链接地址:https://www.31doc.com/p-2900045.html