第5章-數(shù)論中的程序設(shè)計

1、第五章 數(shù)論中的程序設(shè)計,沈云付yfshen@staff.shu.edu.cn,上海大學(xué)計算機工程與科學(xué)學(xué)院,本章主要內(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

2、 從跳獸問題談起,例1：跳獸問題：問題描述： 一只神奇的野獸，它跳一步的長度是某個部落的人們所走步長的m倍，它只在一條長度為n步長的道路上來回不停地跳動。當(dāng)它接近道路的一個端點，但余下距離又不足它的一步時，它會先跳到端點，再折回，其折回的距離是剛才一跳未跳完部分的長度。要求捕捉這只野獸，方法就是把捕捉工具放到這只野獸面前，距離是人一步長的地方。問能否捕捉到這只野獸？請你幫助酋長解決這個問題。,,圖示,,,,,,1,,輸入：

3、輸入有若干行。每行上有兩個整數(shù)n、m，之間用一個空格隔開，其中n表示道路的長度（步數(shù)），m表示野獸跳的步長，（n?50000，m?2000）。假定野獸在道路的一端，捕捉工具放在野獸前一步長的地方。輸出： 對輸入文件每一行的兩個整數(shù)n、m，確定能不能捕捉到這只野獸？若可以捕捉到，則輸出“possible”，否則輸出“impossible”。,輸入與輸出,輸入樣例：20 312345 6輸出樣例：possibleImposs

4、ible,分析,野獸跳的情況如下：m，2m，3m，…，(k-1)m，…有折回：第k步時恰好到達(dá)終點就回跳,距離是多少？結(jié)論：野獸跳到位置是n、m的線性組合：nx+my進(jìn)一步：要跳到1的位置，需有x，y使 nx+my=1 但滿足nx+my=1 未必保證一定跳到離洞口1步距離，為什么？經(jīng)分析，跳到洞口1的充分和必要的條件是GCD(2n,m)=1,來回跳躍環(huán)形示意圖,,,,5.2 最大公因數(shù)與最小公倍數(shù),1．公約數(shù)和最大公約數(shù)的概

5、念2．最大公約數(shù)的一種求法—分解因子3．最大公約數(shù)性質(zhì)與歐幾里德轉(zhuǎn)輾相除法4．歐幾里德轉(zhuǎn)輾相除法5．歐幾里德算法實現(xiàn),,,實例 求最大公因數(shù),問題描述： 從輸入文件中讀取一組數(shù)據(jù)，求最大公因數(shù)。輸入： 輸入有若干行。每一行上有兩個整數(shù)x，y，是一組測試數(shù)據(jù)，他們之間用一個空格隔開。輸出： 對每一組測試數(shù)據(jù)，每行輸出這兩個整數(shù)的最大公因數(shù)。如無最大公因數(shù)，則標(biāo)明“no GCD”。,輸出樣例：(6,11)=

6、1(0,0) no GCD(5,0)=5,輸入樣例： 6 110 05 0,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ù)

7、：兩個不同時為0的整數(shù)a與b的最大公因數(shù)是其值為最大的公因數(shù)，記作gcd(a, b)。 gcd(24, 30)＝6。,最大公約數(shù)的一種求法—分解因子,因為gcd(a，b)＝gcd(|a|，|b|)，所以可考慮非負(fù)整數(shù)的情況。 通過求因數(shù)，可求a和b的素數(shù)因子分解： a= ，b= 于是整數(shù)a和b的最大公因數(shù)為： gcd(a，b)＝,,,,最大公因數(shù)性質(zhì),性質(zhì)：（1）gcd(a，b)＝

8、gcd(? a，? b)（2）gcd(a，b)＝gcd(a + kb， b)，k為任何整數(shù)（3）gcd(a，b)＝gcd(b，a mod b)（4）如a是非零整數(shù)，那么gcd(a，0)＝|a|,歐幾里德轉(zhuǎn)輾相除法的依據(jù)： gcd(a，b)＝gcd(b，a mod b) 可求整數(shù)a和b的最大公因數(shù),5.2.2 最小公倍數(shù),公倍數(shù)：如果m是a的倍數(shù)并且也是b的倍數(shù)，那么稱m是a與b的公倍數(shù)。最小公倍數(shù)：兩個非零整數(shù)a與b的最小

9、公倍數(shù)是a與b的公倍數(shù)中數(shù)值最小正的數(shù)，記作lcm(a，b)（或簡寫為[a，b]）。lcm(a，b)＝lcm(|a|，|b|) 通過a和b的標(biāo)準(zhǔn)分解，可以求出整數(shù)a和b的最小公倍數(shù)： lcm(a，b)=,最小公倍數(shù)與最大公因數(shù)關(guān)系,5.2.3 歐兒里德算法,給定任意兩個正整數(shù)a和b,……,,gcd(a，b)=,結(jié)論：,求最大公因數(shù)的遞歸程序,用歐幾里德轉(zhuǎn)輾相除法構(gòu)造一個求最大公因數(shù)的遞歸程序。輸入：非負(fù)整數(shù)a、b

10、返回：a和b的最大公因數(shù)long gcd(long a, long b){ long m; if ((b==0)&(a==0)) //表示無最大公因數(shù) return -1; if (b==0) return a; else m=gcd(b, a%b); return m;},求最大公因數(shù)的無遞歸程序,int gcd(int a,int b) {int c;if(a ==0) re

11、turn b; while(b!=0) c=b,b=a%b,a=c; return a;},,5.3 利用歐幾里德算法求整系數(shù)一次不定方程ax+by=c的解,算法思想：利用求a,b的最大公因數(shù)的轉(zhuǎn)輾相除過程，進(jìn)行多次逆推，使最大公因數(shù)的表示式最終表示為a與b的線性組合ax+by (x與y可能為0或負(fù)數(shù)) 。此時，d＝gcd(a,b)做法：將歐幾里德算法進(jìn)行推廣，使得該算法不僅能得出任意兩個正整數(shù)a和b的最大公因數(shù)

12、d，而且還能計算出滿足下式的整數(shù)x和y：d=ax+by,,反向遞推,輾轉(zhuǎn)相除過程的逆推,記,類似地，記,一般地，,于是有整數(shù)x和y滿足： d＝gcd(a，b)＝ax+by,擴展歐幾里德算法-遞歸實現(xiàn),輸入整數(shù)a、b，返回gcd(a，b)和對應(yīng)等式ax+by=d中的x,y。long extend_gcd(long a, long b, long &x,long &y){ long t,m; if ((b

13、==0)&(a==0)) return -1;//表示無最大公因數(shù) if (b==0){ x=1;y=0; return a; } else { m=extend_gcd(b,a % b,x,y); t=x;x=y;y=t-(a/b)*y; } return m;},擴展歐幾里德算法-無遞歸實現(xiàn),int extend_gcd(int a, int b,

14、int *x, int *y){int x0,x1,x2, y0,y1,y2;int r0,r1,r2, q;if((a== 0)&&(b==0)){*x=0; *y=0;return -1; } //gcd(a,b)不存在if((a== 0)&&(b!=0)){//a=0時不存在a的乘法逆元*x = 0; *y = 1 ;return b;},

15、if((b == 0) &&(a!=0)) {//b=0時不存在b的乘法逆元*x = 1; *y = 0 ;return a;}if((a!= 0) &&(b!=0)){ x0=0; x1=1; r0= a; y0 = 1; r1 = b;r2=r0 % r1;y1 =0- r0/r1;x2=1;y2=y1;,擴展歐幾里德算法-無遞歸實現(xiàn)(續(xù)

16、),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;return r2;} },mx+ny=c的整數(shù)解算法,設(shè)d=gcd(m, n)，記m=ad，n=bd求特解：求整系數(shù)方程mx

17、+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 模和同余模和同余：設(shè)a、b和m均為整數(shù)，且m>0。如果a和b被m除所得的余數(shù)相同，那么

18、稱a和b關(guān)于模m是同余的，記作,幾個等價定義：,,同余性質(zhì),4、設(shè) ， ，,,,那么,1、2、3、,(1)(2)(3),5、費馬小定理：設(shè)a，p為正整數(shù)，且p為素數(shù)，(p, a)=1， 那么,剩余類與簡化剩余系,剩余類：對于整數(shù)a及模m，則集合A={ x | x≡a (mod m) }稱為模m關(guān)于a的一個剩余類。簡化剩余

19、系：設(shè)m為正整數(shù)，在與m互素的所有剩余類中，每一個類中取一個數(shù)，構(gòu)成一個集合X，則X稱為模m的一個簡化剩余系。舉例： 例1：若p是素數(shù)，則{1，2，3，…，p-1}是模p的一個簡化剩余系。 例2：{1，5，7，11}是模12的一個簡化剩余系。,5.4.2 模線性方程,相當(dāng)于求,根據(jù)前面求 的步驟：,（1）求 ，使,否則， 有d個解,（4）

20、 的所有解可寫為：,（3）由 ，改寫得：,于是 的一個解為：,方程與同余式求解舉例,（2）求（3）求,例：（1）求,,5.5 求mod m的逆元素算法,對整數(shù)a，滿足ax ? 1(mod m)的解x稱為a關(guān)于模m的逆元素。是前面模線性方程的特例。結(jié)論：對整數(shù)a，m（m>0）, ax?1(mod m)有解，當(dāng)且僅當(dāng)，gcd(a，m)=1也可用直接用擴展歐幾里得算法進(jìn)

21、行求解。,,求 的算法,,,舉例,求解：（1）（2）（3）（4）,求mod m的逆元素的無遞歸程序：,long mod_reverse(long a, long m){long y=0,x=1,r=a%m, q, t, mm=m;//初始化if(r<0)r=r+m;while((m%r) != 0) {a=m; m=r;q= a/m; r=a % m;t=x; x=y-x

22、*q; y=t;}if(r!=1) return 0;if(x<0) x=x+mm;return x;},5.6 模線性方程組與中國剩余定理,“韓信點兵”問題 ： 有兵一列，三三數(shù)之余二，五五數(shù)之余三，七七數(shù)之余二，問兵幾何？,,可寫成數(shù)學(xué)表示形式，求x,求解模線性方程組,,中國剩余定理,,求解步驟,,例：解同余方程組,中國剩余定理—程序?qū)崿F(xiàn),long ChinaRemainder(int m0[], in

23、t b[]){long d,x,y,n,m=1,a=0; int i;for (i=1; i<= n ; i++) m=m*m0[i];for (i=1; i<= n ; i++) {MM=m / m0[i];extend_gcd(MM, m0[i], &x, &y); //或x=mod_reverse(M, m0[i]);a=(a+m0[i]

24、*x*b[i]) % m;}return a;},5.7 模冪運算與素數(shù)測試,模冪運算就是在一個模下計算一個冪的值，即計算 (a，r和m是正整數(shù)),,素數(shù)測試就是指，在盡可能短的時間內(nèi)，盡可能精確地判斷一個整數(shù)是否是素數(shù)。通過費馬小定理來判定一個整數(shù)的素性，因此求模冪是重要任務(wù)。,5.7.1 模冪運算,（1）模冪運算1—累次計算法：d＝ ar mod m ＝(…((((a mod m)*a

25、) mod m)*a)mod m…*a)mod m 算法,long modular_power1(long a, long r, long m){ long d=1, k; a=a % m; for(k=0；k<r; k++）d =(a*d) % m; return d;},5.7.1 模冪運算,（2）模冪運算2—快速計算法 將r化為二進(jìn)制數(shù)的形式( bkbk-1…b2b1b0)，然后反復(fù)

26、平方取余數(shù)。然后從最低位開始，自右至左逐位掃描。每次迭代時．用到下面兩個恒等式中的；,模取冪運算—快速計算實現(xiàn),long modular_power1(long a, long r,long m){ long d,t; d=1;t=a; while (r>0){ if ((r%2)==1) d=(d*t) % m； r=r/2; t=t*t % m; }

27、 return d;},,,,練習(xí),計算,,,5.7.2 素數(shù)測試,費馬小定理：設(shè)a，p為正整數(shù)，且p為素數(shù)，(p, a)=1， 那么,,有例外，如2340 ? 1（mod 341），但341是合數(shù)。,素數(shù)測試：設(shè)a、n為正整數(shù) （1）若 ，則n一定為合數(shù) （2）若 ，則幾乎可以肯定地確認(rèn)n為素數(shù)，因出錯概率很小,Miller-Rabin素數(shù)測試算法框架,輸入：n與a（a在2

28、，…，n-1這些數(shù)中隨機取值）輸出：true或false S1. 設(shè)(bk,bk-1,…,b1,b0)為n-1的二進(jìn)制表示S2. d =1S3. For i=k downto 0 do x=d d= (d*d) mod n if ((d=1) and (x?1) and (x?n-1)) then return true if (bi=1) the

29、n d= (d*a)(mod n) End ForS4. if (d ? 1) then return true S5. return false,歐拉定理,設(shè)a和m 是整數(shù)，（m>0）。記?(m)是1到m的整數(shù)中與m互素的整數(shù)的個數(shù)，則a?(m) ≡1 (mod m)。費馬小定理是歐拉定理的特例,5.8 二次剩余與Pell方程,5.8.1 二次剩余 二次剩余：給定素數(shù)p和不被p整除的整數(shù)a。如果有整數(shù)x，使得

30、x2≡a (mod p)，那么稱a為p的二次剩余；否則就稱a為p的二次非剩余。勒讓德符號,,雅可比符號：對兩個非零整數(shù)a，b，（b>0），如果存在整數(shù)x，使得x2≡a (mod b)，那么稱a是b的二次剩余，記為,二次剩余與勒讓德符號,a為模p的二次剩余的充要條件為：,a為模p的二次非剩余的充要條件為：,勒讓德符號計算,（1）（2）（3）（4）（5）,,,,,,已知 的最?。ㄕ┙鈞0，y0,其一般整

31、數(shù)解x，y由 確定,5.8.2 Pell方程,形如 的不定方程式叫佩爾（Pell）方程，其中整數(shù)D不是平方數(shù)，D>0，N=-1，1，-4或4。,特例：,5.9 實例研究,5.9.1 Magic Horse 5.9.2 階乘問題 5.9.3 郵票問題 5.9.4 Josephus問題 5.9.5 負(fù)數(shù)進(jìn)制轉(zhuǎn)換 5.9.6 數(shù)塔問題5.9.7 幸運數(shù) 5.9.8 哥德巴赫猜想,

32、,5.9.1 Magic Horse,問題描述： 在一個無窮大的棋盤上,有一個Magic Horse，它能跳一個a?b的矩形，這只Magic horse能走遍整個棋盤嗎?如下面的棋盤所示的是該Magic Horse跳2?1的矩形的8種情形，類似于國際象棋中馬的走法。輸入： 輸入文件的第一行有一個整數(shù)n，表示有n組測試數(shù)據(jù)，接下來有n行，每行上有兩個整數(shù)a、b，之間用一個或多個空格隔開，（n?20，a?60000，b?6000

33、0）。,,輸出： 對輸入文件的每一組測試數(shù)據(jù)a、b，確定這Magic Horse能走遍整個棋盤。若可以到走遍整個棋盤，則輸出“Yes！”，否則輸出“No！”,分析,只要能從一個格子移動到相鄰的格子，本問題就解決了任何兩個相鄰的格子的坐標(biāo)之和，他們的奇偶性一定是不相同的。由此可以肯定a和b一定是奇偶性相異的。 每次行走的增量一定是a，b的線性組合，即(a, b), (a, -b), (-a, b), (-a, -b) (b,

34、a), (b, -a), (-b, a), (-b, -a)的線性組合。當(dāng)前位置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=p1 * a + q1 * b ，dy=p2 * a + q2 * b其中

35、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一定能使Magic Horse走遍天下呢?答案是肯定的！

36、為什么？理由參見書本。,參考程序：很簡單，略,5.9.2 階乘問題,問題描述： 對一個整數(shù)n，求出n！中末尾0的個數(shù)。 輸入 輸入有若干行。每一行上有一個整數(shù)T，是測試數(shù)據(jù)組數(shù)，接著有T行，每一行包含一個確定的正整數(shù)n，1≤1000000000。輸出 對輸入行中的每一個數(shù)據(jù)n，輸出一行，其內(nèi)容是n！中末尾0的個數(shù)。,輸入與輸出樣例,,分析,“n!末尾0的個數(shù)”，就是指這個數(shù)總共有幾個10因子，而10又能表

37、示成2和5的乘積。顯然，因子2的個數(shù)肯定不少于因子5的個數(shù)。為此只需考察n!中5的個數(shù)”。n?。絥×(n-1)×(n-2)×…×1，因此可以用n除以5就可得到1~n中能被5整除的數(shù)的個數(shù)。但是這不是所有因子5的個數(shù)，因為1~n 中有的數(shù)可以被5整除好幾次。所以必須將n/5再除以5，得到1~n中能被25整除的數(shù)的個數(shù),…。依次循環(huán)進(jìn)行，直到這個數(shù)為0。,計算公式,計算n!末尾0的個數(shù)的公式,程序

38、片斷,int count=0;cin>>n;do {n/=5;count+=n;}while(n);cout<<count<<endl;,5.9.3 郵票問題,問題描述： 郵政總局每年都要發(fā)行許多郵票。如郵局里只有面值6角和8角兩種郵票，而你需要貼的郵票為4元4角，那么你可以用6張6角和一張8角的郵票去貼就可以了。但如你需要貼的郵資為14元5角，甚至

39、郵資是1元時，你就無法用這兩種郵票去貼了。如果兩張郵票為1分和8分，那么任何郵資都可以解決。如果兩張郵票為3分和8分，那么情況又如何呢？ 給你兩種郵票，現(xiàn)在請你確定有多少種情況是無法用這兩種郵票去貼的，你是程序員請幫助他們解決這個問題。,,輸入： 輸入有若干行測試數(shù)據(jù)，最多20行。每行上有兩個整數(shù)A、B，之間用一個空格隔開，（1?n?65000，1?m?65000），他們表示兩張郵票的面值。輸出： 對每一行輸入的兩個

40、整數(shù)A、B，如果有無窮多種情況不能用這兩張郵票來貼，那么輸出“infinite”，否則輸出不能用這兩張郵票來貼的郵資個數(shù)。對每一行測試，輸出一行。,輸入與輸出樣例,輸入樣例：60 801 83 8輸出樣例：infinite07,分析,本問題實際上是給定兩個面值為A、B的郵票，求不能表示成Ax+By形式的郵資的個數(shù)。 采用窮舉法進(jìn)行統(tǒng)計，超時；方法不可行。 如d=gcd(A,B)>1，那么不能表示成Ax+By 形式

41、的郵資的個數(shù)有無窮多，如以下數(shù)都不是Ax+By 形式：1、1+A?B、1+2?A?B、…、1+n?A?B、… 如d=gcd(A,B)=1，結(jié)果如何？,在0到AB-1內(nèi)有 個整數(shù)m可以寫成 m=As+Bt 的形式，s，t是非負(fù)整數(shù)。,分析,以下設(shè)d=gcd(A,B)=1。結(jié)論：值至少為AB的郵資都是可以用這兩種郵票支付的。不能支付的不超過AB-1

42、個，而且可以用一個公式表示。需證明以下幾點：不妨設(shè)A<B。對整數(shù)n，0<n<B，有整數(shù)x、y，使n=Ax+By，且滿足0<x≤B-1，|y|≤A-1。對任何整數(shù)m，只要滿足m?AB，就有非負(fù)整數(shù)s，t，使 m =As+Bt,結(jié)論,若gcd(A,B)=1，則有有限種郵資不能表示成Ax+By的形式。當(dāng)m>=AB時，任何m均可表示成Ax+By的形式，x>=0，y>=0。不能表示成Ax+By形

43、式的數(shù)的個數(shù)為,參考程序：易，略,5.9.4 Josephus問題,問題描述： Josephus問題：一群小孩圍成一圈，任意給定一個數(shù)m，從第一個小孩開始，順時針方向數(shù)，每數(shù)到第m個小孩時，該小孩便離開。小孩不斷離開，圈子不斷縮小。最后剩下的一個小孩是勝利者。究竟勝利者是第幾個小孩呢？輸入： 有若干組測試數(shù)據(jù)。每一行有一個整數(shù)num，m，分別代表小孩個數(shù)和每隔多少小孩數(shù)數(shù)。num，m≤10000。輸出： 對每一組測試數(shù)

44、據(jù)，單行輸出獲勝的小孩的編號。,輸入與輸出樣例,輸入樣例：10 810 2輸出樣例：15,分析,方法一：模擬法實際模擬數(shù)小孩出列的過程。用一個數(shù)組表示小孩圍成圈。對每個小孩賦以一個序號值作為小孩的標(biāo)志。采用 “加1求模”，當(dāng)數(shù)到數(shù)組尾的時候，下一個數(shù)組下標(biāo)值可以算得為0，從而回到數(shù)組首以繼續(xù)整個過程。設(shè)：Max=10000;小孩最大個數(shù) num為小孩個數(shù)，a[Max]; 小孩數(shù)組 每次數(shù)m個小孩，便讓該小孩

45、離開；下標(biāo)加1求模，使下標(biāo)到達(dá)尾部后能返回到數(shù)組頭。,參考代碼一：見下頁,,#includeusing namespace std;int main(){const int Max=10000; int num,m, a[Max]; while(cin>>num>>m){ for(int i=0;i<num;i++) a[i]=i+1; //小孩編號 int k

46、=1; //標(biāo)識處理第k個小孩的離開 int i=-1; //初值 while(1){//圈中數(shù)m個小孩 for(int j=0;j<m;){ i=(i+1)%num;if(a[i]!=0) j++; },if(k==num) break; //該小孩是最后一個嗎？ //是，則為勝利者 a[i]=0;//標(biāo)識該小孩離開 k++;//準(zhǔn)備處

47、理圈中的 //下一個小孩 } cout<<endl; cout<< a[i]<<endl; //第a[i]個小孩獲勝 } return 0;},分析,方法二：數(shù)學(xué)方法更改一下報數(shù)的基準(zhǔn)，從0開始數(shù)，那么這num個小孩一字排開，就是：0，1，2，3，…，num-1。算法思想是，從唯一的小孩開始（起始他的標(biāo)號為0），倒推到num次這個小孩的標(biāo)號

48、，最終得到起始狀態(tài)時共有num個小孩時最終的標(biāo)號，即為題目所求。以下的推導(dǎo)類似于數(shù)學(xué)歸納法證明過程：如果只有一個小孩，他的標(biāo)號是0，那么這個小孩的標(biāo)號就是結(jié)果，此時r=0。考慮目前有k-1個小孩的情況：0，1，2，…，r-1，r，r+1，…，k-2，k-1 這里標(biāo)號r就是當(dāng)小孩總數(shù)為k-1個的時候最終的結(jié)果。,,當(dāng)小孩總數(shù)為k時 按照新定義的計數(shù)方式，從0開始數(shù)，數(shù)到m-1出列，那么上個數(shù)列在這個孩子沒出列時的編號是多

49、少呢？如下： m，m+1，m+2，…，m+r-1，m+r，m+r+1，…，m+k-2，m+k-1 兩個問題需考慮： 出列的那個小孩沒有考慮進(jìn)去，由于所有小孩是圍成一個圈的，所以，可把標(biāo)號為m-1的這個出列的小孩放在首尾皆可，比如放在前面： m-1，m，m+1，m+2，…，m+r-1，m+r，m+r+1，…，m+k-2，m+k-1小孩圍成個圈，那么這個編號應(yīng)該是從0開始，到k-1結(jié)束。只要把所有的這

50、些編號對k取模即可。新的r值就按照這個變換方法變換即可，于是得到r=(r+m)%k。,參考代碼二,#include using namespace std;int main() {int num,m,rwhile(cin>>num>>m) {r=0;for(int k=1;k<=num;++k) r=(r+m)%k;cout<<r+1<<endl;}

51、return 0;},5.9.5 負(fù)數(shù)進(jìn)制轉(zhuǎn)換,問題描述（大意）： 設(shè)計一個程序，讀入一個十進(jìn)制數(shù)和一個負(fù)進(jìn)制的基數(shù)，并將此十進(jìn)制數(shù)轉(zhuǎn)換成為此負(fù)進(jìn)制下的數(shù)： -R∈{-2,-3,-4,......-20} 例如，十進(jìn)制數(shù)-15，相當(dāng)于-2進(jìn)制數(shù)110001：因110001=1*(-2)5+1*(-2)4+0*(-2)3+0*(-2)2+0*(-2)1+1*(-2)0,,輸入 輸入的每行有兩個數(shù)據(jù)N、-R。 N是十

52、進(jìn)制數(shù)，（-32768≤N≤32767），-R是負(fù)進(jìn)制數(shù)的基數(shù)。輸出 相對于每組輸入，應(yīng)輸出此負(fù)進(jìn)制數(shù)及其基數(shù)，若此基數(shù)超過10，則參照十六進(jìn)制的方式處理。,,輸入與輸出樣例,分析,采用與正數(shù)進(jìn)制的轉(zhuǎn)換相類似的方法。對負(fù)數(shù)進(jìn)制，每次取的余數(shù)保證在0~R-1之間，就可以直接輸出。例如-R=-16，則余數(shù)應(yīng)該在0~15。所以用?！?”運算符的時候必須注意檢查是不是在該范圍（可能在-R+1~0），否則就調(diào)整。調(diào)整的方法是：

53、 if （余數(shù)<0）{ 余數(shù)=余數(shù)+R;商=商+1; },數(shù)碼轉(zhuǎn)換表,char change[21]= {'0','1','2','3','4','5','6','7','8','9','A','B',&

54、#39;C','D','E','F','G','H','I','J','K'};,,#include using namespace std;char change[21]={'0','1','2', '3', '4'

55、;,'5','6','7','8','9','A','B', 'C', 'D','E','F','G','H','I','J','K'};int main() { lon

56、g int r,m,base,i,k; char a[1000]; while(cin>>m>>base){ k=m; memset(a,0,sizeof(a)); i=0; while(true){ r=m%base; m=m/base;,if(r=0;i--) cout<<a[i]; cout<

57、;<" (base " <<base; cout<< ")"<<endl; } return 0;},任意范圍基數(shù)轉(zhuǎn)換表,char map(int temp){if(temp<=9)return '0'+temp;elsereturn 'A'+(temp-10);},

58、5.9.6 數(shù)塔問題,問題描述 對任意正整數(shù)n，求由n層n構(gòu)成的數(shù)的個位數(shù)。輸入 輸入文件的第1行是整數(shù)T，（0<T<=50），接下來的T行每行有一個整數(shù)n，（0<n<=1010）。輸出 對輸入中的每個n，對應(yīng)于輸出中的一行，內(nèi)容是由n層n構(gòu)成的數(shù)的個位數(shù)。,輸入與輸出樣例,,分析,設(shè)n的個位數(shù)為a，即，或n=10q+a，再設(shè) 的個位數(shù)為A，指數(shù)為m，那么由

59、 得 A= 。,分情況對a進(jìn)行討論：a=0~9如果a=0，1，5或6，那么A仍分別為0，1，5或6。 如果a=2，那么21? 2，22? 4，23? 8，24? 6，25? 2 (mod 10)2的冪2t的個位數(shù)循環(huán)出現(xiàn)，周期是4 。如設(shè)指數(shù)t=4k+r，r=1，2，3，4，那么2t的個位數(shù)僅與r有關(guān)。,分析,(a=2)：只需

60、計算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。再設(shè)q=2p+s。周期是4。設(shè)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。

61、,分析,如果a=7，n=10q+7，周期是4 。若q為奇數(shù)，則n被4除的余數(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ù),問題描述 中國人認(rèn)為8是一個幸運數(shù)字。鮑勃也認(rèn)為是這樣，而且他有他自己的幸運數(shù) L?，F(xiàn)在他要構(gòu)造他的幸運數(shù)，該數(shù)是僅由數(shù)字8組成且是L的倍數(shù)中最

62、小的那個正整數(shù)。輸入 輸入有多組測試數(shù)據(jù)，每一組僅由一行上的一個正整數(shù)L構(gòu)成，(1<= L<= 2,000,000,000)。最后一組測試數(shù)據(jù)后面的一行是一個0。輸出 對每組測試數(shù)據(jù)，先輸出測試數(shù)據(jù)的編號（從1開始），接著輸出鮑勃的幸運數(shù)的長度，如果鮑勃不能構(gòu)造他的幸運數(shù)，那么輸出0。,分析,設(shè)輸入的數(shù)為L，設(shè)所求數(shù)的最短長度為k，即幸運數(shù)為H=,因為H是L的倍數(shù)，所以有整數(shù)q，使,上述等式左邊無2t(t>

63、3)因子。 Case 1：L有因子16，那么無法找到這個幸運數(shù)H Case 2：L有因子5，那么無法找到這個幸運數(shù)H Case 3：L有因子2t(t<4)。設(shè)L= 2tm，m為無有因子5的奇數(shù)。,Case 3進(jìn)一步討論,表明 是m的倍數(shù) 所以有 這里，(9m，10)=1。 由歐拉定理，可得 由 得 由于k是所求數(shù)的最小長度，因此必有,,,,,,,,Case

64、3算法,計算9m，并求歐拉函數(shù)值?(9m)，記M= ?(9m) 。求M的素因子分解，在M的因子中從較小的因子開始作為k，嘗試驗證 。判斷：如果成立，那么就找到最小的k，終止查找。,,5.9.8 哥德巴赫猜想,問題描述 哥德巴赫是一位德國的業(yè)余數(shù)學(xué)家。1742年，他寫信給當(dāng)時的數(shù)學(xué)家歐拉，信中提出如下猜想： 每個大于4的偶數(shù)都可以寫成兩個奇素數(shù)之和。 例如：8 = 3 + 5，3 和5都是

65、奇素數(shù)， 20 = 3 + 17 = 7 + 13 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23. 直到現(xiàn)在，仍未證明該猜想是否是真的。不管怎樣，你的任務(wù)是對于100萬以內(nèi)的偶數(shù)驗證哥德巴赫猜想。,,輸入 有多組測試數(shù)據(jù)，每組測試數(shù)據(jù)由一個偶數(shù)n構(gòu)成（6≤n < 1000000）。 當(dāng)輸入是0時表示輸入結(jié)束。 輸出 對每種測試數(shù)據(jù)，輸出形如n = a + b的表達(dá)式

66、，其中a和b是奇素數(shù)，加號應(yīng)該用空格隔開，如下面的輸出樣例。如果有多對奇素數(shù)滿足，僅取差b – a最大的一組。如果沒有這樣的素數(shù)對，那么輸出“Goldbach's conjecture is wrong.”,輸入與輸出樣例,輸入樣例 820420 輸出樣例 8 = 3 + 520 = 3 + 1742 = 5 + 37,分析,對于偶數(shù)n，可以取不大于n/2的奇數(shù)p，記q=n-p，即寫n=p+q。本題測試數(shù)據(jù)較弱

67、，可用常規(guī)的判定素數(shù)的埃拉托色尼篩法做，直接判定p和q是否為素數(shù)。為求滿足差b–a最大的一組，只要從3開始到不大于n/2的奇數(shù)依次作為p。當(dāng)n<1000000時，采用常規(guī)方法，有超時的可能。也可嘗試用Miller-Rabin素數(shù)測試該算法并不能保證待測整數(shù)一定是素數(shù)，但對素數(shù)測試的正確性隨著測試次數(shù)的增加而增加。以下程序中采用了二次測試。,練習(xí)：四個素數(shù)之和問題,歐拉證明素數(shù)有無窮多個。但每個整數(shù)能表示成四個素數(shù)之和嗎？我也

68、不知道這一答案，希望你能幫助我。我希望你能高效率地解決這一問題。輸入：每行輸入一個整數(shù)N（N<=10000000），它是你需要把它表示成四個素數(shù)之和的數(shù)。輸入直到文件結(jié)束為止。輸出：對于每個輸入行都有一個輸出行，每行包含符合要求的四個素數(shù)。如果該數(shù)不能表示為四個素數(shù)之和，那么輸出一行“Impossible.”。也可能有多組解，任何合理的解都將被接受。,輸入與輸出舉例,輸入樣例243646 輸出樣例3 11 2 73