




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
初等数论程耀第1页,共23页,2023年,2月20日,星期日素数和合数算术基本定理:任意正整数n可以写成n=2a1*3a2*5a3*…,其中a1,a2,a3等为非负整数素数的判定:①判定函数②筛法求素数③miller_rabin素性判定第2页,共23页,2023年,2月20日,星期日素数的判定boolIs_prime(intn){ intt=(int)sqrt(n); for(inti=2;i<=t;i++) if(n%i==0) returnfalse; returntrue;}第3页,共23页,2023年,2月20日,星期日筛法求素数思考:如果一个数是合数,那么它的素因子都比它小???这样说来:如果我们的当前数是a,那么所有a的倍数(当然是2倍以上啦)都不会是素数,可以这样看吧?于是,我们可以一种新的素数判定方法。第4页,共23页,2023年,2月20日,星期日筛法求素数方法:每次用一个素数,去筛掉所有它的倍数。举个例子:23456789101112131415161718192021222324252627282930①筛去2的倍数,剩下357911131517192123252729②筛去3的倍数,剩下57111317192529。。。。。。注意:开头的数一定是素数???第5页,共23页,2023年,2月20日,星期日筛法求素数boolprime[maxn];//时间复杂度O(n)???voidinit(){ memset(prime,0,sizeof(prime)); for(inti=4;i<maxn;i+=2) prime[i]=1; for(inti=3;i<maxn;i+=2) if(!prime[i]){ for(intj=i*i;j<maxn;j+=i) prime[j]=1; }}第6页,共23页,2023年,2月20日,星期日miller_rabin素性判定miller_rabin是一种概率型的算法,不是确定型的。但是,只要运行次数足够多,一般出错的概率是非常小的,一般10次就好了!算法复杂度是O((logn)^3)算法的正确性是基于费马小定理。费马小定理:对于素数p和任意整数a,有 a^(p-1)=1(modp)。反过来,满足a^(p-1)= 1(modp),p也几乎一定是素数。第7页,共23页,2023年,2月20日,星期日miller_rabin算法分析boolmiller_rabin(LLn){ if(n<2)returnfalse; if(n==2)returntrue; if(!(n&1))returnfalse; for(inti=1;i<=12;i++){ LLa=random(n-2)+1; if(witness(a,n))returnfalse; } returntrue;}第8页,共23页,2023年,2月20日,星期日witness函数witness函数用来搜集n是合数的证据。boolwitness(LLa,LLn){ LLm=n-1;intt=0;LLy; while(!(m&1)){m>>=1;t++;}//这个地方是通过一个推论来优化的,x^2=1(modn),当那个n是合数的时候,就会出现非平凡平方根! LLx=quick_mod(a,m,n); for(inti=1;i<=t;i++){ y=muti(x,x,n); if(y==1&&x!=1&&x!=n-1)returntrue;x=y; } if(y!=1)returntrue; elsereturnfalse; }第9页,共23页,2023年,2月20日,星期日快速幂取模题目:求出m^n(modp)的值,其中m<=10000,n<=100000000。分析:如果直接边乘然后边取模,直接导致TLE!我们需要一个更优的算法。我们可以发现:这其中包含着大量的重复的子问题,利用分治的思想可以大大减小运算量。举个例子:2^7=2^4*2^2*2^1,而2^t到2^(2t)只需要累乘就好了。
第10页,共23页,2023年,2月20日,星期日快速幂取模算法分析把指数看成一个二进制数,从低位到高位依次判断是否为1。如果是1,就要乘以2^t,否则,就不需要乘上2^t.其中,ak等系数只能取0,或者1。如果取1的话,那么要乘以对应的a^(2^k). 算法复杂度O(logn)第11页,共23页,2023年,2月20日,星期日快速幂取模代码分析
intquick_mod(inta,intn){ intt=a,ret=1; while(n){ if(n&1) ret=ret*t%n; n>>=1; //n右移两位,相当于除2 t=t*t%n; } returnret;}PS:与快速幂取模类似的还有矩阵快乘,这里不展开第12页,共23页,2023年,2月20日,星期日最大公约数(gcd)普通算法:求出c=min(a,b),如果找到c|a&& c|b,那么c减一,然后循环继续,直到找到c满足条件为止。欧几里得算法:intgcd(inta,intb){ returnb?gcd(b,a%b):a;}第13页,共23页,2023年,2月20日,星期日欧几里得算法的证明证明:令m是a,b的公约数,而a可以表示为 a=n*b+r,其中r>=0&&r<b 那么r=a-n*b,可以知道r能够被m整除。 同理:如果m是r和b的公约数。那么, a=n*b+r,所以,m也能够整除a. 由上面的两条可知:a,b和b,r具有相同的公约数,故欧几里得算法成立。第14页,共23页,2023年,2月20日,星期日扩展欧几里得算法应用:常用来求解形如a*x+b*y=gcd(a,b)的二元一次不定方程代码如下: voidextended_gcd(inta,intb,int&x,int&y){ if(b==0){x=1;y=0;return;} extended_gcd(b,a%b,x,y); inttemp=x; x=y; y=temp-a/b*y;}第15页,共23页,2023年,2月20日,星期日扩展欧几里得算法分析证明:令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;第16页,共23页,2023年,2月20日,星期日扩展欧几里得算法的注意事项①形如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/d*t 其中:t是整数。第17页,共23页,2023年,2月20日,星期日a关于模n的乘法逆元什么是乘法逆元?如果a*b=1(modn),那么b就是a关于模n的乘法逆元,此时,也可以称作a与b互为乘法逆元。第18页,共23页,2023年,2月20日,星期日乘法逆元的应用题目:输出C(n,m)%p,其中p是一个素数。n<10000.思考:如果使用边除边模的方法,也会有出现大数,导致精度溢出。(a/b)%p!=((a%p)/(b%p))%p;解决方案:除以一个数并取模,就相当于是乘以它的逆元然后再取模。第19页,共23页,2023年,2月20日,星期日如何求解乘法逆元上式等价a*x+b*n=1的解,所以可以应用扩展欧几里得算法来求出x的值。为了保证x是正整数,通常需要加上: x=(x%n+n)%n;intinv(inta,intn){ intx,y; extended_gcd(a,n,x,y); x=(x%n+n)%n; returnx;}第20页,共23页,2023年,2月20日,星期日扩展阅读AekdyCoin的博客:/new/aekdycoinAC神牛被称为数学帝,里面收录了好多数论方面的知识,其中最经典的就是各种大数取模.笨小孩的博客:/sunhaowenprime/item/d7faf6ea35b6dee4fb42ba2a这个博客收录了各种数论题的分类,有志于做数论专题的同学可以参考。第21页,共23页,2023年,2月20日,星期日最后一页qinz大牛的博客:http://qinz.maybe.im/最值得一看的就是qi
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025湖北黄冈市红安县事业单位引进专业人才33人笔试模拟试题及答案解析
- 企业落实《规定》专项检查表
- 趣味运动会广播稿(合集15篇)
- 语法知识:单句与复句
- 部编版语文知识树
- 趣味科普知识
- 述职报告与下一步工作计划
- 身韵提沉说课
- 中国越剧•唱腔知到课后答案智慧树章节测试答案2025年春浙江艺术职业学院
- 遗憾文案励志工作总结
- 权责体系手册
- 2025年合肥职业技术学院单招职业技能测试题库附答案
- 2024初级会计职称考试题库(附参考答案)
- 供水管道知识培训课件
- 2025年烟草行业专卖执法人员法律知识考试100题及答案
- 2025年四川省对口招生(旅游类)《前厅服务与管理》考试复习题库(含答案)
- 《木版年画》课件-版画制作
- 2025年江西环境工程职业学院高职单招职业技能测试近5年常考版参考题库含答案解析
- 2025年《科学道德与学术规范》心得体会模版(4篇)
- 《金融科技概论》完整全套课件
- 2025年新疆生产建设兵团兴新职业技术学院高职单招高职单招英语2016-2024年参考题库含答案解析
评论
0/150
提交评论