1、第五、六講：黃麗韶ly_sa,第五章數(shù)論中的程序設計,本章主要內(nèi)容,5.1從跳獸問題談起5.2最大公因數(shù)與最小公倍數(shù)5.3求整系數(shù)一次不定方程ax+by=c的解5.4求解模線性方程5.5求模m的逆元素算法5.6模線性方程組與中國剩余定理5.7模取冪運算與素數(shù)測試5.8二次剩余與Pell方程5.9實例研究,1,2,3,4,5,6,7,8,9,5.1從跳獸問題談起,例1：跳獸問題：問題描述：一只神奇的野獸，它跳一步的長度是某個部落的人們所走步長的m倍，它只在一條長度為n步長的道路上來回不停地跳動。當它接近道路的一個端點，但余下距離又不足它的一步時，它會先跳到端點，再折回，其折回的距離是剛才一跳未跳

2、完部分的長度。要求捕捉這只野獸，方法就是把捕捉工具放到這只野獸面前，距離是人一步長的地方。問能否捕捉到這只野獸？請你幫助酋長解決這個問題。,圖示,1,輸入：輸入有若干行。每行上有兩個整數(shù)n、m，之間用一個空格隔開，其中n表示道路的長度（步數(shù)），m表示野獸跳的步長，（n50000，m2000）。假定野獸在道路的一端，捕捉工具放在野獸前一步長的地方。輸出：對輸入文件每一行的兩個整數(shù)n、m，確定能不能捕捉到這只野獸？若可以捕捉到，則輸出“possible”，否則輸出“impossible”。,輸入與輸出,輸入樣例：203123456輸出樣例：possibleImpossible,分析,野獸跳的情況如

3、下：m，2m，3m，(k-1)m，有折回：第k步時恰好到達終點就回跳,距離是多少？結論：野獸跳到位置是n、m的線性組合：nx+my進一步：要跳到1的位置，需有x，y使nx+my=1那么gcd(n,m)=1是否能保證能跳到1的位置呢？當m為偶數(shù)的情況下，不可能捕捉到野獸。,來回跳躍環(huán)形示意圖,5.2最大公因數(shù)與最小公倍數(shù),1公約數(shù)和最大公約數(shù)的概念2最大公約數(shù)的一種求法分解因子3最大公約數(shù)性質(zhì)與歐幾里德轉(zhuǎn)輾相除法4歐幾里德轉(zhuǎn)輾相除法5歐幾里德算法實現(xiàn),實例求最大公因數(shù),問題描述：從輸入文件中讀取一組數(shù)據(jù)，求最大公因數(shù)。輸入：輸入有若干行。每一行上有兩個整數(shù)x，y，是一組測試數(shù)據(jù)，他們之間用一個空

4、格隔開。輸出：對每一組測試數(shù)據(jù)，每行輸出這兩個整數(shù)的最大公因數(shù)。如無最大公因數(shù)，則標明“noGCD”。,輸出樣例：(6,11)=1(0,0)noGCD(5,0)=5,輸入樣例：6110050,5.2.1公因數(shù)和最大公因數(shù)的概念,公因數(shù)：如果d是a的因數(shù)并且也是b的因數(shù)，則d是a與b的公因數(shù)例：30的正因數(shù)：1，2，3，5，6，10，15、30；24的正因數(shù)：1，2，3，4，6，12，24；24與30的正公因數(shù)有：1、2、3、6。1是任意兩個整數(shù)的公因數(shù)；最大公因數(shù)：兩個不同時為0的整數(shù)a與b的最大公因數(shù)是其值為最大的公因數(shù)，記作gcd(a,b)。gcd(24,30)6。,最大公約數(shù)的一種求法分

5、解因子,因為gcd(a，b)gcd(|a|，|b|)，所以可考慮非負整數(shù)的情況。通過求因數(shù)，可求a和b的素數(shù)因子分解：a=，b=于是整數(shù)a和b的最大公因數(shù)為：gcd(a，b),最大公因數(shù)性質(zhì),性質(zhì)：（1）gcd(a，b)gcd(a，b)（2）gcd(a，b)gcd(a+kb，b)，k為任何整數(shù)（3）gcd(a，b)gcd(b，amodb)（4）如a是非零整數(shù)，那么gcd(a，0)|a|,歐幾里德轉(zhuǎn)輾相除法的依據(jù)：gcd(a，b)gcd(b，amodb)可求整數(shù)a和b的最大公因數(shù),5.2.2最小公倍數(shù),公倍數(shù)：如果m是a的倍數(shù)并且也是b的倍數(shù)，那么稱m是a與b的公倍數(shù)。最小公倍數(shù)：兩個非零整數(shù)a

6、與b的最小公倍數(shù)是a與b的公倍數(shù)中數(shù)值最小正的數(shù)，記作lcm(a，b)（或簡寫為a，b）。lcm(a，b)lcm(|a|，|b|)通過a和b的標準分解，可以求出整數(shù)a和b的最小公倍數(shù)：lcm(a，b)=,最小公倍數(shù)與最大公因數(shù)關系,5.2.3歐兒里德算法,給定任意兩個正整數(shù)a和b,gcd(a，b)=,結論：,求最大公因數(shù)的遞歸程序,用歐幾里德轉(zhuǎn)輾相除法構造一個求最大公因數(shù)的遞歸程序。輸入：非負整數(shù)a、b返回：a和b的最大公因數(shù)longgcd(longa,longb)longm;if(b=0),求最大公因數(shù)的無遞歸程序,intgcd(inta,intb)intc;if(a=0)returnb;w

7、hile(b!=0)c=b,b=a%b,a=c;returna;,5.3利用歐幾里德算法求整系數(shù)一次不定方程ax+by=c的解,算法思想：利用求a,b的最大公因數(shù)的轉(zhuǎn)輾相除過程，進行多次逆推，使最大公因數(shù)的表示式最終表示為a與b的線性組合ax+by(x與y可能為0或負數(shù))。此時，dgcd(a,b)做法：將歐幾里德算法進行推廣，使得該算法不僅能得出任意兩個正整數(shù)a和b的最大公因數(shù)d，而且還能計算出滿足下式的整數(shù)x和y：d=ax+by,反向遞推,輾轉(zhuǎn)相除過程的逆推,記,類似地，記,一般地，,于是有整數(shù)x和y滿足：dgcd(a，b)ax+by,擴展歐幾里德算法-遞歸實現(xiàn),輸入整數(shù)a、b，返回gcd(

8、a，b)和對應等式ax+by=d中的x,y。longextend_gcd(longa,longb,long,擴展歐幾里德算法-無遞歸實現(xiàn),intextend_gcd(inta,intb,int*x,int*y)intx0,x1,x2,y0,y1,y2;intr0,r1,r2,q;if(a=0),if(b=0),擴展歐幾里德算法-無遞歸實現(xiàn)(續(xù)),while(r1%r2)!=0)r0=r1;r1=r2;q=r0/r1;x2=x0-x1*q;y2=y0-y1*q;x0=x1;x1=x2;y0=y1;y1=y2;r2=r0%r1;*x=x2;*y=y2;returnr2;,mx+ny=c的整數(shù)解算法

9、,設d=gcd(m,n)，記m=ad，n=bd求特解：求整系數(shù)方程mx+ny=d的一個整數(shù)解x0，y0，求一般解：若d不是c的因數(shù)，則整系數(shù)方程mx+ny=c無整數(shù)解；若d是c的因數(shù)，記c=gd，則整系數(shù)方程mx+ny=c一般解為：x=gx0+bt,y=gy0-at,t為任何整數(shù),舉例,求下列整系數(shù)方程的整數(shù)解：,答案：略,5.4求解模線性方程,5.4.1模和同余模和同余：設a、b和m均為整數(shù)，且m0。如果a和b被m除所得的余數(shù)相同，那么稱a和b關于模m是同余的，記作,幾個等價定義：,同余性質(zhì),4、設，,那么,1、2、3、,(1)(2)(3),5、費馬小定理：設a，p為正整數(shù)，且p為素數(shù)，(p

10、,a)=1，那么,剩余類與簡化剩余系,剩余類：對于整數(shù)a及模m，則集合A=x|xa(modm)稱為模m關于a的一個剩余類。簡化剩余系：設m為正整數(shù)，在與m互素的所有剩余類中，每一個類中取一個數(shù)，構成一個集合X，則X稱為模m的一個簡化剩余系。舉例：例1：若p是素數(shù)，則1，2，3，p-1是模p的一個簡化剩余系。例2：1，5，7，11是模12的一個簡化剩余系。,5.4.2模線性方程,相當于求,根據(jù)前面求的步驟：,（1）求，使,否則，有d個解,（4）的所有解可寫為：,（3）由，改寫得：,于是的一個解為：,方程與同余式求解舉例,（2）求（3）求,例：（1）求,5.5求modm的逆元素算法,對整數(shù)a，滿足

11、ax1(modm)的解x稱為a關于模m的逆元素。是前面模線性方程的特例。結論：對整數(shù)a，m（m0）,ax1(modm)有解，當且僅當，gcd(a，m)=1也可用直接用擴展歐幾里得算法進行求解。,求的算法,舉例,求解：（1）（2）（3）（4）,求modm的逆元素的無遞歸程序：,longmod_reverse(longa,longm)longy=0,x=1,r=a%m,q,t,mm=m;/初始化if(r0)r=r+m;while(m%r)!=0)a=m;m=r;q=a/m;r=a%m;t=x;x=y-x*q;y=t;if(r!=1)return0;if(x0)x=x+mm;returnx;,5.6

12、模線性方程組與中國剩余定理,“韓信點兵”問題：有兵一列，三三數(shù)之余二，五五數(shù)之余三，七七數(shù)之余二，問兵幾何？,可寫成數(shù)學表示形式，求x,求解模線性方程組,中國剩余定理,求解步驟,例：解同余方程組,中國剩余定理程序?qū)崿F(xiàn),longChinaRemainder(intm0,intb)longd,x,y,n,m=1,a=0;inti;for(i=1;i=n;i+)m=m*m0i;for(i=1;i0）。記(m)是1到m的整數(shù)中與m互素的整數(shù)的個數(shù)，則a(m)1(modm)。費馬小定理是歐拉定理的特例,5.8二次剩余與Pell方程,5.8.1二次剩余二次剩余：給定素數(shù)p和不被p整除的整數(shù)a。如果有整數(shù)x

13、，使得x2a(modp)，那么稱a為p的二次剩余；否則就稱a為p的二次非剩余。勒讓德符號,雅可比符號：對兩個非零整數(shù)a，b，（b0），如果存在整數(shù)x，使得x2a(modb)，那么稱a是b的二次剩余，記為,二次剩余與勒讓德符號,a為模p的二次剩余的充要條件為：,a為模p的二次非剩余的充要條件為：,勒讓德符號計算,（1）（2）（3）（4）（5）,已知的最?。ㄕ┙鈞0，y0,其一般整數(shù)解x，y由確定,5.8.2Pell方程,形如的不定方程式叫佩爾（Pell）方程，其中整數(shù)D不是平方數(shù)，D0，N=-1，1，-4或4。,特例：,5.9實例研究,5.9.1MagicHorse5.9.2階乘問題5.9.3

14、郵票問題5.9.4Josephus問題5.9.5負數(shù)進制轉(zhuǎn)換5.9.6數(shù)塔問題5.9.7幸運數(shù)5.9.8哥德巴赫猜想,5.9.1MagicHorse,問題描述：在一個無窮大的棋盤上,有一個MagicHorse，它能跳一個ab的矩形，這只Magichorse能走遍整個棋盤嗎?如下面的棋盤所示的是該MagicHorse跳21的矩形的8種情形，類似于國際象棋中馬的走法。輸入：輸入文件的第一行有一個整數(shù)n，表示有n組測試數(shù)據(jù)，接下來有n行，每行上有兩個整數(shù)a、b，之間用一個或多個空格隔開，（n20，a60000，b60000）。,輸出：對輸入文件的每一組測試數(shù)據(jù)a、b，確定這MagicHorse能走遍

15、整個棋盤。若可以到走遍整個棋盤，則輸出“Yes！”，否則輸出“No！”,分析,只要能從一個格子移動到相鄰的格子，本問題就解決了任何兩個相鄰的格子的坐標之和，他們的奇偶性一定是不相同的。由此可以肯定a和b一定是奇偶性相異的。每次行走的增量一定是a，b的線性組合，即(a,b),(a,-b),(-a,b),(-a,-b)(b,a),(b,-a),(-b,a),(-b,-a)的線性組合。當前位置pos=t1*(a,b)+t2*(a,-b)+t3*(-a,b)+t4*(-a,-b)+t5*(b,a)+t6*(b,-a)+t7*(-b,a)+t8*(-b,-a)。,增量,pos=(dx,dy)，其中dx=

16、p1*a+q1*b，dy=p2*a+q2*b其中p1=t1+t2-t3-t4，q1=t5+t6-t7-t8，p2=t5-t6+t7-t8，q2=t1-t2+t3-t4于是要能走到相鄰的格子，必有dx=1或dy=1。即只要求出p，q，使a*p+b*q=1,兩個必須滿足的條件,（1）a+b是奇數(shù)，即a,b奇偶性不同；（2）a,b互質(zhì)，即gcd(a,b)=1。,滿足這兩個條件的a,b一定能使MagicHorse走遍天下呢?答案是肯定的！為什么？理由參見書本。,參考程序：很簡單，略,5.9.2階乘問題,問題描述：對一個整數(shù)n，求出n！中末尾0的個數(shù)。輸入輸入有若干行。每一行上有一個整數(shù)T，是測試數(shù)據(jù)組

17、數(shù)，接著有T行，每一行包含一個確定的正整數(shù)n，11000000000。輸出對輸入行中的每一個數(shù)據(jù)n，輸出一行，其內(nèi)容是n！中末尾0的個數(shù)。,輸入與輸出樣例,分析,“n!末尾0的個數(shù)”，就是指這個數(shù)總共有幾個10因子，而10又能表示成2和5的乘積。顯然，因子2的個數(shù)肯定不少于因子5的個數(shù)。為此只需考察n!中5的個數(shù)”。n！n(n-1)(n-2)1，因此可以用n除以5就可得到1n中能被5整除的數(shù)的個數(shù)。但是這不是所有因子5的個數(shù)，因為1n中有的數(shù)可以被5整除好幾次。所以必須將n/5再除以5，得到1n中能被25整除的數(shù)的個數(shù),。依次循環(huán)進行，直到這個數(shù)為0。,計算公式,計算n!末尾0的個數(shù)的公式,程

18、序片斷,intcount=0;cinn;don/=5;count+=n;while(n);coutcount1，那么不能表示成Ax+By形式的郵資的個數(shù)有無窮多，如以下數(shù)都不是Ax+By形式：1、1+AB、1+2AB、1+nAB、如d=gcd(A,B)=1，結果如何？,在0到AB-1內(nèi)有個整數(shù)m可以寫成m=As+Bt的形式，s，t是非負整數(shù)。,分析,以下設d=gcd(A,B)=1。結論：值至少為AB的郵資都是可以用這兩種郵票支付的。不能支付的不超過AB-1個，而且可以用一個公式表示。需證明以下幾點：不妨設AB。對整數(shù)n，0n=0，y=0。不能表示成Ax+By形式的數(shù)的個數(shù)為,參考程序：易，略,

19、5.9.4Josephus問題,問題描述：Josephus問題：一群小孩圍成一圈，任意給定一個數(shù)m，從第一個小孩開始，順時針方向數(shù)，每數(shù)到第m個小孩時，該小孩便離開。小孩不斷離開，圈子不斷縮小。最后剩下的一個小孩是勝利者。究竟勝利者是第幾個小孩呢？輸入：有若干組測試數(shù)據(jù)。每一行有一個整數(shù)num，m，分別代表小孩個數(shù)和每隔多少小孩數(shù)數(shù)。num，m10000。輸出：對每一組測試數(shù)據(jù)，單行輸出獲勝的小孩的編號。,輸入與輸出樣例,輸入樣例：108102輸出樣例：15,分析,方法一：模擬法實際模擬數(shù)小孩出列的過程。用一個數(shù)組表示小孩圍成圈。對每個小孩賦以一個序號值作為小孩的標志。采用“加1求模”，當數(shù)到

20、數(shù)組尾的時候，下一個數(shù)組下標值可以算得為0，從而回到數(shù)組首以繼續(xù)整個過程。設：Max=10000;小孩最大個數(shù)num為小孩個數(shù)，aMax;小孩數(shù)組每次數(shù)m個小孩，便讓該小孩離開；下標加1求模，使下標到達尾部后能返回到數(shù)組頭。,參考代碼一：見下頁,#includeusingnamespacestd;intmain()constintMax=10000;intnum,m,aMax;while(cinnumm)for(inti=0;inum;i+)ai=i+1;/小孩編號intk=1;/標識處理第k個小孩的離開inti=-1;/初值while(1)/圈中數(shù)m個小孩for(intj=0;jm;)i=(

21、i+1)%num;if(ai!=0)j+;,if(k=num)break;/該小孩是最后一個嗎？/是，則為勝利者ai=0;/標識該小孩離開k+;/準備處理圈中的/下一個小孩coutendl;coutainumm)r=0;for(intk=1;k=num;+k)r=(r+m)%k;coutr+1mbase)k=m;memset(a,0,sizeof(a);i=0;while(true)r=m%base;m=m/base;,if(r=0;i-)coutai;cout(basebase;cout)endl;return0;,任意范圍基數(shù)轉(zhuǎn)換表,charmap(inttemp)if(temp=9)re

22、turn0+temp;elsereturnA+(temp-10);,5.9.6數(shù)塔問題,問題描述對任意正整數(shù)n，求由n層n構成的數(shù)的個位數(shù)。輸入輸入文件的第1行是整數(shù)T，（0T=50），接下來的T行每行有一個整數(shù)n，（0n=1010）。輸出對輸入中的每個n，對應于輸出中的一行，內(nèi)容是由n層n構成的數(shù)的個位數(shù)。,輸入與輸出樣例,分析,設n的個位數(shù)為a，即，或n=10q+a，再設的個位數(shù)為A，指數(shù)為m，那么由得A=。,分情況對a進行討論：a=09如果a=0，1，5或6，那么A仍分別為0，1，5或6。如果a=2，那么212，224，238，246，252(mod10)2的冪2t的個位數(shù)循環(huán)出現(xiàn)，周期

23、是4。如設指數(shù)t=4k+r，r=1，2，3，4，那么2t的個位數(shù)僅與r有關。,分析,(a=2)：只需計算m被4除得的余數(shù)。因n為偶數(shù)，所以m也為偶數(shù)。如果n本身是2，那么A=4；在其他情況下，m的指數(shù)是也是偶數(shù)2p，此時m能被4除盡，即r=4。此時A=6。根據(jù)2.類似的討論，以下簡單地討論：如果a=3，n=10q+3。再設q=2p+s。周期是4。設m的指數(shù)t=4k+r，r=1，2，3，4。若s=0，則m被4除的余數(shù)是3，此時A=7。若s=1，則m被4除的余數(shù)仍是1，此時A=3。如果a=4，周期是2。m是一個偶數(shù)，此時A=6。,分析,如果a=7，n=10q+7，周期是4。若q為奇數(shù)，則n被4除的

24、余數(shù)是1，A=7。若q為偶數(shù)，則n被4除的余數(shù)是3，A=3。如果a=8，n=10q+8，周期是4。冪m的底是n，為偶數(shù)，其指數(shù)也是偶數(shù)。在這種情況下，A=6。如果a=9，周期是2。A=9,5.9.7幸運數(shù),問題描述中國人認為8是一個幸運數(shù)字。鮑勃也認為是這樣，而且他有他自己的幸運數(shù)L?，F(xiàn)在他要構造他的幸運數(shù)，該數(shù)是僅由數(shù)字8組成且是L的倍數(shù)中最小的那個正整數(shù)。輸入輸入有多組測試數(shù)據(jù)，每一組僅由一行上的一個正整數(shù)L構成，(1=L3)因子。Case1：L有因子16，那么無法找到這個幸運數(shù)HCase2：L有因子5，那么無法找到這個幸運數(shù)HCase3：L有因子2t(t4)。設L=2tm，m為無有因子5的奇數(shù)。,Case3進一步討論,表明是m的倍數(shù)所以有這里，(9m，10)=1。由歐拉定理，可得由得由于k是所求數(shù)的最小長度，因此必有,Case3算法,計算9m，并求歐拉函數(shù)值(9m)，記M=(9m)。求M的素因子分解，在M的因子中從較小的因子開始作為k，嘗試驗證。判斷：如果成立，那么就找到最小的k，終止查找。,5.9.8哥德巴赫猜想,問題描述哥德巴赫是一位德國的業(yè)余數(shù)學家。1742年，他寫信給當時的數(shù)學家歐拉