提高班第四講初等數(shù)論

提高班第四講初等數(shù)論第1頁，共42頁，2023年，2月20日，星期六目錄1、素數(shù)2、快速冪取模3、唯一質(zhì)因子分解定理3、最大公約數(shù)（歐幾里得算法）4、擴展歐幾里得算法5、同余以及線性同余方程6、特殊的線性同余方程組：中國剩余定理第2頁，共42頁，2023年，2月20日，星期六素數(shù)1、判斷n是否為素數(shù)for(inti=2;i*i<=n;i++)if(n%i==0){flag=1;break;}2、如果要求10^6區(qū)間內(nèi)的素數(shù)呢？概念：除了1和此整數(shù)自身外，不能被其他自然數(shù)整除的數(shù)。第3頁，共42頁，2023年，2月20日，星期六2）給定一個范圍（求這個范圍內(nèi)的素數(shù)），進行如下步驟：

0.從2開始，2是第一個素數(shù)。也是第一個新素數(shù)。取出2。

1.篩掉所有新素數(shù)的倍數(shù)。

2.留下來的數(shù)里面第一個（最小的）是新素數(shù)。取出這個新素數(shù)。

3.重復(fù)1和2直到?jīng)]有數(shù)存在。Eratosthenes篩法第4頁，共42頁，2023年，2月20日，星期六memset(flag,0,sizeof(flag));for(inti=2;i*i<=1000000;i++)if(!flag[i]){for(intg=i;g<=1000000;g+=i)flag[g]=1;}第5頁，共42頁，2023年，2月20日，星期六快速冪取模1、10^8怎么求？3、10^（10^8）%9999?2、10^180呢？第6頁，共42頁，2023年，2月20日，星期六1.模取運算的性質(zhì)

(1)(a+b)%c=((a%c)+(b%c))%c

(2)(a*b)%c=((a%c)*b)%c第7頁，共42頁，2023年，2月20日，星期六10.__int64fn(__int64a,__int64k)

11.{

12.if(k==0)return1;

13.if(k==1)returna%mod;

14.__int64tmp1=fn(a,k/2);

15.__int64tmp2=tmp1*tmp1%mod;

16.if(k&1)returntmp2*a%mod;

17.returntmp2;

18.}(a^k)%mod第8頁，共42頁，2023年，2月20日，星期六快速冪（風(fēng)格簡潔）__int64quickmod(__int64x,__int64n){__int64pw=1;while(n>0){if(n&1)//n&1等價于(n%2)==1pw*=x;x*=x;n>>=1;//n>>=1等價于n/=2}returnpw;}第9頁，共42頁，2023年，2月20日，星期六質(zhì)因子分解定理唯一因子分解唯一質(zhì)因子分解定理：合數(shù)a僅能以一種方式，寫成如下的乘積形式：a=p1e1p2e2…prer其中pi為素數(shù)，p1<p2<…<pr，且ei為正整數(shù)。第10頁，共42頁，2023年，2月20日，星期六那么怎么求的一個合數(shù)n的所有素因子呢？暴力法：1、先求出每一個n的素因子，然后窮舉篩選法的妙用：思路不明白沒關(guān)系，看代碼第11頁，共42頁，2023年，2月20日，星期六for(inti=2;i*i<=n;){if(n%i==0){cout<<i<<"";while(n%i==0){n/=i;}}elsei++;

}if(n!=1)cout<<n<<endl;第12頁，共42頁，2023年，2月20日，星期六其他一些關(guān)于約數(shù)的公式第13頁，共42頁，2023年，2月20日，星期六初等數(shù)論的概念除法定理，余數(shù)除法定理：對任意整數(shù)a和任意正整數(shù)n，存在唯一的整數(shù)q和r，使得a=qn+r，其中0≤r<n。值q成為除法的商，值r=a(modn)稱為除法的余數(shù)。第14頁，共42頁，2023年，2月20日，星期六公約數(shù)與最大公約數(shù)d是a的約數(shù)并且也是b的約數(shù)，則d是a和b的公約數(shù)。兩個不同時為0的整數(shù)a和b的最大公約數(shù)表示為gcd(a,b)。第15頁，共42頁，2023年，2月20日，星期六互質(zhì)數(shù)：如果兩個整數(shù)a與b只有公因數(shù)1，即如果gcd(a,b)=1，則a與b稱為互質(zhì)數(shù)（互素）。定理：對任意整數(shù)a，b和p，如果gcd(a,p)=1且gcd(b,p)=1，則gcd(ab,p)=1。第16頁，共42頁，2023年，2月20日，星期六最大公約數(shù)gcd（最大公因子）Euclidean算法求兩個正整數(shù)a和b的gcd。先令r0為a，r1為b，接著執(zhí)行如下運算：第17頁，共42頁，2023年，2月20日，星期六GCD遞歸定理：對任意非負整數(shù)a和任意正整數(shù)b，gcd(a,b)=gcd(b,amodb)。第18頁，共42頁，2023年，2月20日，星期六

例：求8251和6105的最大公因數(shù)。

8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4

最后除數(shù)37是148和37的最大公因數(shù)，也就是8251與6105的最大公因數(shù)。第19頁，共42頁，2023年，2月20日，星期六歐幾里德算法（輾轉(zhuǎn)相除法）：intgcd(a,b){//returnb?gcd(b,a%b):a;if(!b)returna;returngcd(b,a%b);}第20頁，共42頁，2023年，2月20日，星期六LCM(LeastCommonMultiple)有了GCD,LCM就好辦了LCM(a,b)=a*b/GCD(a,b)實際上最好寫成a/GCD(a,b)*b思考：為什么下面的寫法好？第21頁，共42頁，2023年，2月20日，星期六擴展歐幾里得算法擴展歐幾里得定理：對于不完全為0的非負整數(shù)a，b，gcd（a，b）表示a，b的最大公約數(shù)d，必然存在整數(shù)對x，y，使得gcd（a，b）=d=ax+by。

擴展歐幾里德算法是用來在已知a,b求解一組x，y使得ax+by=Gcd(a,b)=d

第22頁，共42頁，2023年，2月20日，星期六設(shè)a>b。1、顯然當(dāng)b=0時，gcd（a，b）=a。此時x=1，y=0；

2、ab！=0時，設(shè)ax1+by1=gcd(a,b);bx2+(amodb)y2=gcd(b,amodb);根據(jù)樸素的歐幾里德原理有g(shù)cd(a,b)=gcd(b,amodb);第23頁，共42頁，2023年，2月20日，星期六則:ax1+by1=bx2+(amodb)y2;即:ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2;根據(jù)恒等定理得：x1=y2;y1=x2-(a/b)*y2;這樣我們就得到了求解x1,y1的方法：x1，y1的值基于x2，y2.上面的思想是以遞歸定義的，因為gcd不斷的遞歸求解一定會有個時候b=0，所以遞歸可以結(jié)束。第24頁，共42頁，2023年，2月20日，星期六voidextend_Eulid(inta,intb){ inttemp; if(b==0){ x=1;y=0;q=a;} //q是什么？ else{ extend_Eulid(b,a%b); temp=x; x=y; y=temp-a/b*y;}} 第25頁，共42頁，2023年，2月20日，星期六擴展歐幾里得典型例題：POJ1061青蛙的約會TIPS：抽象模型，建立方程就已成功了一半第26頁，共42頁，2023年，2月20日，星期六根據(jù)題意，青蛙若想碰面的話，則必有(x+mt)-(y+nt)=p*L;(p為任意整數(shù))。方程化為：(m-n)t-(y-x)=pL;則有((m-n)t-(y-x))modL=0。即為：(m-n)tmodL=y-x為線性同余方程。此方程有解當(dāng)且僅當(dāng)y-x能被m-n和L的最大公約數(shù)(記為gcd(m-n,L))整除,即gcd(m-n,L)|y-x有解。這時，如果x0是方程的一個解，即當(dāng)t=x0時，(m-n)tmodL=y-x成立。第27頁，共42頁，2023年，2月20日，星期六

設(shè)d=gcd(m-n,L)，根據(jù)擴展歐幾里得定理，則必存在整數(shù)對(r,s)使得(m-n)*r+L*s=d;則可得t=r*(y-x)/d。第28頁，共42頁，2023年，2月20日，星期六scanf("%I64d%I64d%I64d%I64d%I64d",&x,&y,&m,&n,&L);__int64d=exGcd(n-m,L,xx,yy);if((x-y)%d!=0)cout<<"Impossible"<<endl;else{xx=xx*((x-y)/d);ints=L/d;xx=(xx%s+s)%s;printf("%I64d\n",xx);}

第29頁，共42頁，2023年，2月20日，星期六設(shè)m≠0，若m∣a－b，即a－b＝km，則稱a同余于b模m，記為a、b關(guān)于模m同余的充要條件是整數(shù)a和b被同一正整數(shù)m除時，有相同的余數(shù)。

同余第30頁，共42頁，2023年，2月20日，星期六同余的性質(zhì)

第31頁，共42頁，2023年，2月20日，星期六

例：求3406寫成十進位數(shù)時的個位數(shù).根據(jù)題意是要求a滿足3406≡a（mod10）顯然32≡9≡9（mod10），34≡1（mod10），從而3404≡1（mod10），因此3406≡3404×32≡9（mod10）所以個位數(shù)是9.這個可以用我們之前學(xué)的的方法做嗎？第32頁，共42頁，2023年，2月20日，星期六模的逆元若m≥1，（a，m）＝1，則存在c使得

ca≡1（modm）我們把c稱為是a對模m的逆，記為

a－1（modm）或a－1第33頁，共42頁，2023年，2月20日，星期六求解模線性方程定理：方程ax=b(modn)對于未知量x有解，當(dāng)且僅當(dāng)gcd(a,n)|b定理：方程ax=b(modn)或者對模n有d個不同的解，其中d=gcd(a,n)或者無解。第34頁，共42頁，2023年，2月20日，星期六求解模線性方程定理：假設(shè)方程ax=b(modn)有解（即有d|b，其中d=gcd(a,n)），x0是該方程的任意一個解，則該方程對模n恰有d個不同的解，分別為：xi=x0+i(n/d)(i=1,2,…,d-1)。第35頁，共42頁，2023年，2月20日，星期六求解模線性方程定理：設(shè)d=gcd(a,n)，假定對整數(shù)x’和y’，有d=ax’+ny’。如果d|b，則方程ax=b(modn)有一個解的值為x0，滿足x0=x’(b/d)modn。第36頁，共