初等數(shù)論程耀

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

2、求素數(shù)思考：如果一個數(shù)是合數(shù)，那么它的素因子都比它??？這樣說來：如果我們的當前數(shù)是 a ,那么所有 a的倍數(shù)（當然是2倍以上啦）都不會是素數(shù)，可以這樣看吧？于是，我們可以一種新的素數(shù)判定方法。第4頁，共23頁，2022年，5月20日，13點34分，星期一篩法求素數(shù)方法：每次用一個素數(shù)，去篩掉所有它的倍數(shù)。舉個例子：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 。注意：開頭的數(shù)一定是素數(shù)？第5頁，共23頁，2022年，5月20日，13點34分，星期一篩法求素數(shù)bool prime maxn ;/時間復雜度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頁，共23頁，2022年，5月20日，13點34分，星期一miller_ra

4、bin素性判定miller_rabin是一種概率型的算法，不是確定型的。但是，只要運行次數(shù)足夠多，一般出錯的概率是非常小的，一般10次就好了！算法復雜度是 O(logn)3)算法的正確性是基于費馬小定理。費馬小定理：對于素數(shù)p和任意整數(shù)a，有a(p-1)=1(mod p)。反過來，滿足a(p-1)=1(mod p),p也幾乎一定是素數(shù)。第7頁，共23頁，2022年，5月20日，13點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+;/這個地方是通過一個推論來優(yōu)化的，x2=1(mod n),當那個n是合數(shù)的時候，就會出現(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頁，共23頁，2022年，5月20日，13點34分，星期一快速冪取模題目：求出mn ( mod p) 的值，其中 m=10000, n=1;/n右移兩位，相當于除

6、2t = t * t %n;return ret ; PS：與快速冪取模類似的還有矩陣快乘，這里不展開第12頁，共23頁，2022年，5月20日，13點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頁，共23頁，2022年，5月20日，13點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頁，共23頁，2022年，5月20日，13點34分，星期一擴展歐幾里得算法應用：常用來求解形如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頁，共23頁，2022年，5月20日，13點34分，星期一擴展歐幾里得算法分析證明：令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頁，2022年，5月20日，13點34分，星期一擴展歐幾里得算法的注意事項形如a*x + b*y = c的方程,如果gcd(a,b)能夠整除c,那么此方程有解，否則無解。并且它的特解形式為x=c/gcd(a,b)*x0 , y=c/gcd(a,b

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

10、一個數(shù)并取模，就相當于是乘以它的逆元然后再取模。第19頁，共23頁，2022年，5月20日，13點34分，星期一如何求解乘法逆元上式等價a*x+b*n=1的解，所以可以應用擴展歐幾里得算法來求出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頁，共23頁，2022年，5月20日，13點34分，星期一擴展閱讀AC神牛被稱為數(shù)學帝，里面收錄了好多數(shù)論方面的知識，其中最經典的就是各種大數(shù)取模.笨小孩的博客：這個博客收錄了各種數(shù)論題的分類，有志于做數(shù)論專題的同學可以參考。第21頁，共23頁，2022年，5月20日，13點34分，星期一最后一頁 最值得一看的就是qinz大牛的ACM裝逼錄， 我已經看了不知道多少遍了，但是，總是感覺百看不厭。強烈推薦大家看看！ 最后的話：可能每個ac