初等數論程耀

初等數論程耀第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++;}//這個地方是通過一個推論來優(yōu)化的，x^2=1(modn),當那個n是合數的時候，就會出現(xià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！我們需要一個更優(yōu)的算法。我們可以發(fā)現(xiàn)：這其中包含著大量的重復的子問題，利用分治的思想可以大大減小運算量。舉個例子：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減一，然后循環(huán)繼續(xù)，直到找到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的值。把①②兩式聯(lián)立，消去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.思考：如果使用邊除邊模的方法，也會有出現(xiàn)大數，導致精度溢出。(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