《初等数论程耀》PPT课件

《《初等数论程耀》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、XDU_ACM----初等数论——程耀素数和合数算术基本定理：任意正整数n可以写成n=2a1*3a2*5a3*…,其中a1,a2,a3等为非负整数素数的判定：①判定函数②筛法求素数③miller_rabin素性判定素数的判定boolIs_prime(intn){intt=(int)sqrt(n);for(inti=2;i<=t;i++）if(n%i==0)returnfalse;returntrue;}筛法求素数思考：如果一个数是合数，那么它的素因子都比它小？？？这样说来：如果我们的当前数是a,那么所有a的倍数（当然是2倍以上啦）都不会是素数，可以这样看吧？于是，我们

2、可以一种新的素数判定方法。筛法求素数方法：每次用一个素数，去筛掉所有它的倍数。举个例子：23456789101112131415161718192021222324252627282930①筛去2的倍数，剩下357911131517192123252729②筛去3的倍数，剩下57111317192529。。。。。。注意：开头的数一定是素数？？？筛法求素数boolprime[maxn];//时间复杂度O(n)???voidinit(){memset(prime,0,sizeof(prime));for(inti=4;i

3、inti=3;i

4、{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;}witness函数witness函数用来搜集n是合数的证据。boolwitness(LLa,LLn){LLm=n-1;intt=0;LLy;while(!(m&1)){m>>=1;t++;}//这个地方是通过一个推论来优化的，x^2=1(modn),当那个n是合数的时候，就会出现非平凡平方

5、根！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;}快速幂取模题目：求出m^n(modp)的值，其中m<=10000,n<=100000000。分析：如果直接边乘然后边取模，直接导致TLE！我们需要一个更优的算法。我们可以发现：这其中包含着大量的重复的子问题，利用分治的思想可以大大减小运算量。举个例子：2^7=2^4*2^2*2^1,而2^t到2^(2t)只需

6、要累乘就好了。快速幂取模算法分析把指数看成一个二进制数，从低位到高位依次判断是否为1。如果是1，就要乘以2^t,否则，就不需要乘上2^t.其中，ak等系数只能取0，或者1。如果取1的话，那么要乘以对应的a^(2^k).算法复杂度O(logn)快速幂取模代码分析intquick_mod(inta,intn){intt=a,ret=1;while(n){if(n&1)ret=ret*t%n;n>>=1;//n右移两位，相当于除2t=t*t%n;}returnret;}PS：与快速幂取模类似的还有矩阵快乘，这里不展开最大公约数（gcd)普通算法：求出c=min(a,b),如

7、果找到c

8、a&&c

9、b,那么c减一，然后循环继续，直到找到c满足条件为止。欧几里得算法：intgcd(inta,intb){returnb?gcd(b,a%b):a;}欧几里得算法的证明证明：令m是a,b的公约数，而a可以表示为a=n*b+r,其中r>=0&&r