初等數(shù)論程耀

1、初等數(shù)論程耀第1頁(yè)，共23頁(yè)，2022年，5月20日，13點(diǎn)34分，星期一素?cái)?shù)和合數(shù)算術(shù)基本定理：任意正整數(shù)n可以寫(xiě)成n=2a1*3a2*5a3*,其中a1,a2,a3等為非負(fù)整數(shù)素?cái)?shù)的判定： 判定函數(shù) 篩法求素?cái)?shù) miller_rabin素性判定第2頁(yè)，共23頁(yè)，2022年，5月20日，13點(diǎn)34分，星期一素?cái)?shù)的判定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;第3頁(yè)，共23頁(yè)，2022年，5月20日，13點(diǎn)34分，星期一篩法

2、求素?cái)?shù)思考：如果一個(gè)數(shù)是合數(shù)，那么它的素因子都比它??？這樣說(shuō)來(lái)：如果我們的當(dāng)前數(shù)是 a ,那么所有 a的倍數(shù)（當(dāng)然是2倍以上啦）都不會(huì)是素?cái)?shù)，可以這樣看吧？于是，我們可以一種新的素?cái)?shù)判定方法。第4頁(yè)，共23頁(yè)，2022年，5月20日，13點(diǎn)34分，星期一篩法求素?cái)?shù)方法：每次用一個(gè)素?cái)?shù)，去篩掉所有它的倍數(shù)。舉個(gè)例子：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 2829 30篩去2的倍數(shù)，剩下3 5 7 9 11 13 15 17 19 21 23 25 27 29篩去3的倍數(shù)，剩下5 7 11 13

3、17 19 25 29 。注意：開(kāi)頭的數(shù)一定是素?cái)?shù)？第5頁(yè)，共23頁(yè)，2022年，5月20日，13點(diǎn)34分，星期一篩法求素?cái)?shù)bool prime maxn ;/時(shí)間復(fù)雜度O(n)?void init ( )memset(prime, 0 ,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;第6頁(yè)，共23頁(yè)，2022年，5月20日，13點(diǎn)34分，星期一miller_ra

4、bin素性判定miller_rabin是一種概率型的算法，不是確定型的。但是，只要運(yùn)行次數(shù)足夠多，一般出錯(cuò)的概率是非常小的，一般10次就好了！算法復(fù)雜度是 O(logn)3)算法的正確性是基于費(fèi)馬小定理。費(fèi)馬小定理：對(duì)于素?cái)?shù)p和任意整數(shù)a，有a(p-1)=1(mod p)。反過(guò)來(lái)，滿足a(p-1)=1(mod p),p也幾乎一定是素?cái)?shù)。第7頁(yè)，共23頁(yè)，2022年，5月20日，13點(diǎn)34分，星期一miller_rabin算法分析bool miller_rabin(LL n) if(n2) return false; if(n=2) return true; if(!(n&1) return f

5、alse; for(int i=1;i=1;t+;/這個(gè)地方是通過(guò)一個(gè)推論來(lái)優(yōu)化的，x2=1(mod n),當(dāng)那個(gè)n是合數(shù)的時(shí)候，就會(huì)出現(xiàn)非平凡平方根！ LL x=quick_mod(a,m,n); for(int i=1;i=t;i+) y=muti(x,x,n); if(y=1 & x!=1 & x!=n-1) return true; x=y; if(y!=1) return true; else return false;第9頁(yè)，共23頁(yè)，2022年，5月20日，13點(diǎn)34分，星期一快速冪取模題目：求出mn ( mod p) 的值，其中 m=10000, n=1;/n右移兩位，相當(dāng)于除

6、2t = t * t %n;return ret ; PS：與快速冪取模類(lèi)似的還有矩陣快乘，這里不展開(kāi)第12頁(yè)，共23頁(yè)，2022年，5月20日，13點(diǎn)34分，星期一最大公約數(shù)（gcd)普通算法：求出c=min( a , b),如果找到c|a&c|b,那么c減一，然后循環(huán)繼續(xù)，直到 找到 c滿足條件為止。歐幾里得算法：int gcd(int a , int b)return b?gcd(b,a%b):a; 第13頁(yè)，共23頁(yè)，2022年，5月20日，13點(diǎn)34分，星期一歐幾里得算法的證明證明：令m是a , b 的公約數(shù)，而a可以表示為a = n*b + r,其中r=0 & rb那么r = a

7、- n*b,可以知道r 能夠被 m 整除。同理：如果m是r 和 b 的公約數(shù)。那么，a=n*b +r,所以，m也能夠整除a.由上面的兩條可知：a,b和b,r具有相同的公約數(shù)，故歐幾里得算法成立。第14頁(yè)，共23頁(yè)，2022年，5月20日，13點(diǎn)34分，星期一擴(kuò)展歐幾里得算法應(yīng)用：常用來(lái)求解形如a*x+b*y=gcd(a,b)的二元一次不定方程代碼如下：void extended_gcd( int a, int b, int &x ,int &y)if(b=0) x=1; y=0; return;extended_gcd(b,a%b,x,y);int temp=x;x=y;y=temp-a/b*

8、y; 第15頁(yè)，共23頁(yè)，2022年，5月20日，13點(diǎn)34分，星期一擴(kuò)展歐幾里得算法分析證明：令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來(lái)替換a%b;然后可以令x=y1,推出y=x1-a/b*y1;第16頁(yè)，共23頁(yè)，2022年，5月20日，13點(diǎn)34分，星期一擴(kuò)展歐幾里得算法的注意事項(xiàng)形如a*x + b*y = c的方程,如果gcd(a,b)能夠整除c,那么此方程有解，否則無(wú)解。并且它的特解形式為x=c/gcd(a,b)*x0 , y=c/gcd(a,b

9、)*y0 (其中 x0,y0是用擴(kuò)展歐幾里得算法求出的解）通解的形式：x=x0 - b/d*ty= y0 + a/d*t其中：t是整數(shù)。第17頁(yè)，共23頁(yè)，2022年，5月20日，13點(diǎn)34分，星期一a關(guān)于模n的乘法逆元什么是乘法逆元？如果a*b=1(mod n),那么b就是a 關(guān)于模n的乘法逆元，此時(shí)，也可以稱(chēng)作a與b互為乘法逆元。第18頁(yè)，共23頁(yè)，2022年，5月20日，13點(diǎn)34分，星期一乘法逆元的應(yīng)用題目：輸出C(n,m)%p,其中p是一個(gè)素?cái)?shù)。n10000.思考：如果使用邊除邊模的方法，也會(huì)有出現(xiàn)大數(shù)，導(dǎo)致精度溢出。 (a/b)%p != (a%p)/(b%p)%p;解決方案：除以

10、一個(gè)數(shù)并取模，就相當(dāng)于是乘以它的逆元然后再取模。第19頁(yè)，共23頁(yè)，2022年，5月20日，13點(diǎn)34分，星期一如何求解乘法逆元上式等價(jià)a*x+b*n=1的解，所以可以應(yīng)用擴(kuò)展歐幾里得算法來(lái)求出x的值。為了保證x是正整數(shù)，通常需要加上：x=(x%n+n)%n；int inv(int a , int n)int x,y;extended_gcd(a,n,x,y);x=(x%n+n)%n;return x;第20頁(yè)，共23頁(yè)，2022年，5月20日，13點(diǎn)34分，星期一擴(kuò)展閱讀AC神牛被稱(chēng)為數(shù)學(xué)帝，里面收錄了好多數(shù)論方面的知識(shí)，其中最經(jīng)典的就是各種大數(shù)取模.笨小孩的博客：這個(gè)博客收錄了各種數(shù)論題的分類(lèi)，有志于做數(shù)論專(zhuān)題的同學(xué)可以參考。第21頁(yè)，共23頁(yè)，2022年，5月20日，13點(diǎn)34分，星期一最后一頁(yè) 最值得一看的就是qinz大牛的ACM裝逼錄， 我已經(jīng)看了不知道多少遍了，但是，總是感覺(jué)百看不厭。強(qiáng)烈推薦大家看看！ 最后的話：可能每個(gè)ac