初等数论程耀

初等数论程耀第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