程序設計實習(II)：算法設計-第13講-高精度計算

1、程序設計實習程序設計實習(II)(II)：算法設計：算法設計- -第第1313講講- -高精度計算高精度計算C語言的輸入輸出語句#include scanf( ) 將輸入讀入變量 printf( ) 將變量內(nèi)容輸出scanf( ) 語句（函數(shù))int scanf( const char int scanf( const char * * , .); , .); 參數(shù)可變的函數(shù)參數(shù)可變的函數(shù)第一個參數(shù)是格式字符串，后面的參數(shù)是變量的地址，第一個參數(shù)是格式字符串，后面的參數(shù)是變量的地址，函數(shù)作用是按照第一個參數(shù)指定的格式，將數(shù)據(jù)讀入函數(shù)作用是按照第一個參數(shù)指定的格式，將數(shù)據(jù)讀入后面的變量后面的變量

2、參數(shù)可變的函數(shù)的參考閱讀參數(shù)可變的函數(shù)的參考閱讀（不要求掌握）不要求掌握）http:/ 返回值 0 成功讀入的數(shù)據(jù)項個數(shù)； 0 沒有項被賦值； EOF 第一個嘗試輸入的字符是EOF(結(jié)束) （對（對POJ上某些題，返回值為上某些題，返回值為EOF可以用來判可以用來判斷輸入數(shù)據(jù)已經(jīng)全部讀完）斷輸入數(shù)據(jù)已經(jīng)全部讀完）printf( ) 語句（函數(shù))int printf( const char int printf( const char * * , .); , .); 參數(shù)可變的函數(shù)參數(shù)可變的函數(shù)第一個參數(shù)是格式字符串，后面的參數(shù)是待輸出的變第一個參數(shù)是格式字符串，后面的參數(shù)是待輸出的變量，函數(shù)作

3、用是按照第一個參數(shù)指定的格式，將后面量，函數(shù)作用是按照第一個參數(shù)指定的格式，將后面的變量在屏幕上輸出的變量在屏幕上輸出 返回值返回值:成功打印的字符數(shù)；成功打印的字符數(shù)； 返回負值為出錯返回負值為出錯%d %d 讀入或輸出讀入或輸出intint變量變量%c %c 讀入或輸出讀入或輸出charchar變量變量%f %f 讀入或輸出讀入或輸出floatfloat變量變量%s %s 讀入或輸出讀入或輸出char char * * 變量變量%lf %lf 讀入或輸出讀入或輸出double double 變量變量%e %e 以科學計數(shù)法格式輸出數(shù)值以科學計數(shù)法格式輸出數(shù)值%x %x 以十六進制讀入或輸出

4、以十六進制讀入或輸出 int int 變量變量%I64d %I64d 讀入或輸出讀入或輸出 _int64 _int64 變量變量(64(64位整數(shù)）位整數(shù)）%p %p 輸出指針地址值輸出指針地址值 %.5lf %.5lf 輸出浮點數(shù)，精確到小數(shù)點后輸出浮點數(shù)，精確到小數(shù)點后5 5位位格式字符串里的格式控制符號：#include int main() int a;char b;char c20;double d = 0;float e = 0;int n = scanf(%d%c%s%lf%f,&a,&b,c,&d,&e);printf(%d %c %s %lf

5、%e %f %d,a,b,c,d,e,e,n);return 0; int n = scanf(%d%c%s%lf%f,&a,&b,c,&d,&e);printf(%d %c %s %lf %e %f %d,a,b,c,d,e,e,n);input: 123a teststring 8.9 9.2output: 123 a teststring 8.900000 9.200000e+000 9.200000 5input: 123ateststring 8.9 9.2output: input: 123 a teststring 8.9 9.2output: 1

6、23 a teststring 8.900000 9.200000e+000 9.200000 5123 a 0.000000 0.000000e+000 0.000000 3#include int main() int a,b;char c;char s20;_int64 n = 9876543210001111;/VC+ 6.0scanf(%d %c,%s%x%I64d,&a,&c,s,&b, &n);printf(%d %x %u %s %p %x %d %I64d,a,a,a,s,s,b,b,n);return 0; input: -28 K,test

7、 ffee 1234567890123456output: -28 ffffffe4 4294967268 test 0012FF60 ffee 65518 1234567890123456#include int main() int a,b;char c;char s20;long long n = 9876543210001111LL;/Dev C+scanf(%d %c,%s%x%I64d,&a,&c,s,&b, &n);printf(%d %x %u %s %p %x %d %I64d,a,a,a,s,s,b,b,n);return 0; input:

8、 -28 K,test ffee 1234567890123456output: -28 ffffffe4 4294967268 test 0012FF60 ffee 65518 1234567890123456#include #include int main()int main() char char * * s; s;scanf(%s,s);scanf(%s,s);return 0;return 0; 錯在何處？錯在何處？常見錯誤：錯在錯在 s s 不知道指向何處，往其指向的地方寫入數(shù)據(jù)，不知道指向何處，往其指向的地方寫入數(shù)據(jù)，不安全不安全char char * * gets(char

9、 gets(char * * s); s);從標準輸入讀取一行到字符串從標準輸入讀取一行到字符串s s如果成功，返回值就是如果成功，返回值就是 s s 地址地址如果失敗，返回值是如果失敗，返回值是 NULLNULL可以根據(jù)返回值是可以根據(jù)返回值是 NULLNULL判定輸入數(shù)據(jù)已經(jīng)讀完判定輸入數(shù)據(jù)已經(jīng)讀完調(diào)用時要確保調(diào)用時要確保 s s 指向的緩沖區(qū)足夠大，否則可能發(fā)生指向的緩沖區(qū)足夠大，否則可能發(fā)生內(nèi)存訪問錯誤內(nèi)存訪問錯誤讀取一行：#include #include int main() int main() char s200;char s200;char char * * p = gets

10、(s); p = gets(s);printf(%s:%s,s,p);printf(%s:%s,s,p);return 0; return 0; input:input:Welcome to Beijing !Welcome to Beijing !讀取一行：output:output:Welcome to Beijing !:Welcome to Beijing !Welcome to Beijing !:Welcome to Beijing !int sscanf(const char int sscanf(const char * * buffer, const char buffer,

11、 const char * * format, address, .);format, address, .);和和scanfscanf的區(qū)別在于，它是從的區(qū)別在于，它是從bufferbuffer里讀取數(shù)據(jù)里讀取數(shù)據(jù)int sprintf(char int sprintf(char * *buffer, const char buffer, const char * *format, format, argument, .);argument, .);和和printfprintf的區(qū)別在于，它是往的區(qū)別在于，它是往bufferbuffer里輸出數(shù)據(jù)里輸出數(shù)據(jù)sscanf 函數(shù)和 sprintf

12、函數(shù)#include int main() int a,b; char c; char s20;char szSrc = -28 K,test ffee 1234567890123456;char szDest200;_int64 n = 9876543210001111;sscanf(szSrc, %d %c,%s%x%I64d,&a,&c,s,&b, &n);sprintf(szDest, %d %x %u %s %p %x %d %I64d,a,a,a,s,s,b,b,n);printf(%s,szDest);return 0; output: -28 f

13、fffffe4 4294967268 test 0012FF60 ffee 65518 1234567890123456例題：POJ2981大整數(shù)加法 (P159)(P159)l問題描述問題描述 求兩個不超過200位的非負整數(shù)的和。l輸入數(shù)據(jù)輸入數(shù)據(jù)l有兩行，每行是一個不超過200位的非負整數(shù)，沒有多余的前導0。l輸出要求輸出要求一行，即相加后的結(jié)果。結(jié)果里不能有多余的前導0，即如果結(jié)果是342，那么就不能輸出為0342。 l輸入樣例輸入樣例2222222222222222222233333333333333333333l輸出樣例輸出樣例55555555555555555555例題：POJ29

14、81大整數(shù)加法 (P159) 解題思路1) 用字符型或整型數(shù)組來存放大整數(shù) an0存放個位數(shù)，an1存放十位數(shù)，an2存放百位數(shù)2）模擬小學生列豎式做加法，從個位開始逐位相加，超過或達到10則進位。 用unsigned an1201保存第一個數(shù)，用unsigned an2200表示第二個數(shù)，然后逐位相加，相加的結(jié)果直接存放在an1中。要注意處理進位。#include #include #define MAX_LEN 201int an1MAX_LEN+10;int an2MAX_LEN+10;char szLine1MAX_LEN+10;char szLine2MAX_LEN+10;int A

15、dd(int nMaxLen , int * an1, int * an2)/將長度最多為 nMaxLen 的大整數(shù) an1和an2 相加，結(jié)果放在an1, /an10,an20對應于個位int nHighestPos = 0;for(int i = 0;i = 10 ) /看是否要進位an1i -= 10;an1i+1 +;/進位if( an1i )nHighestPos = i; /記錄最高位的位置return nHighestPos;int main() scanf(%s, szLine1); scanf(%s, szLine2);int i, j;/庫函數(shù)memset將地址an1開始的

16、sizeof(an1)字節(jié)內(nèi)容置成0/sizeof(an1)的值就是an1的長度/memset函數(shù)在string.h中聲明memset( an1, 0, sizeof(an1);memset( an2, 0, sizeof(an2);/下面將szLine1中存儲的字符串形式的整數(shù)轉(zhuǎn)換到an1中去，/an10對應于個位int nLen1 = strlen( szLine1);for(j =0, i = nLen1 - 1;i = 0 ; i -)an1j+ = szLine1i - 0;int nLen2 = strlen(szLine2);for(j=0, i = nLen2 - 1;i =

17、0 ; i -)an2j+ = szLine2i - 0;int nHighestPos = Add(MAX_LEN,an1,an2);for( i = nHighestPos; i = 0; i - ) printf(%d, an1i);return 0;例題：例題：POJPOJ27362736 大整數(shù)減法大整數(shù)減法問題描述問題描述求2個大的正整數(shù)相減的差 輸入數(shù)據(jù)輸入數(shù)據(jù)第1行是測試數(shù)據(jù)的組數(shù)n，每組測試數(shù)據(jù)占2行，第1行是被減數(shù)a，第2行是減數(shù)b(a b)。每組測試數(shù)據(jù)之間有一個空行，每行數(shù)據(jù)不超過100個字符輸出要求輸出要求n行，每組測試數(shù)據(jù)有一行輸出是相應的整數(shù)差例題：例題：POJP

18、OJ27362736 大整數(shù)減法大整數(shù)減法輸入樣例輸入樣例2 9999999999999999999999999999999999999 9999999999999 5409656775097850895687056798068970934546546575676768678435435345 1輸出樣例輸出樣例99999999999999999999999900000000000005409656775097850895687056798068970934546546575676768678435435344 #include #include #define MAX_LEN 110int

19、an1MAX_LEN;int an2MAX_LEN;char szLine1MAX_LEN;char szLine2MAX_LEN;int Substract( int nMaxLen, int * an1, int * an2) /兩個最多nMaxLen位的大整數(shù)an1減去an2, an1保證大于an2int nStartPos = 0;for( int i = 0;i nMaxLen ; i + ) an1i -= an2i; /逐位減if( an1i = 0 ; i -)an1j+ = szLine1i - 0;int nLen2 = strlen(szLine2);for( j = 0

20、, i = nLen2 - 1;i = 0 ; i -)an2j+ = szLine2i - 0;int nStartPos = Substract( MAX_LEN, an1,an2);for( i = nStartPos; i = 0; i - ) printf(%d, an1i);printf(n); return 0;例題：例題：POJPOJ29802980 大整數(shù)乘法大整數(shù)乘法 問題描述問題描述求兩個不超過200位的非負整數(shù)的積。輸入數(shù)據(jù)輸入數(shù)據(jù)有兩行，每行是一個不超過200位的非負整數(shù)，沒有多余的前導0。輸出要求輸出要求一行，即相乘后的結(jié)果。結(jié)果里不能有多余的前導0，即如果結(jié)果是3

21、42，那么就不能輸出為0342。 輸入樣例輸入樣例1234567890098765432100輸出樣例輸出樣例1219326311126352690000解題思路解題思路用unsigned an1200和unsigned an2200分別存放兩個乘數(shù)，用aResult400來存放積。計算的中間結(jié)果也都存在aResult中。aResult長度取400是因為兩個200位的數(shù)相乘，積最多會有400位。an10, an20, aResult0都表示個位。一個數(shù)的第i位和另一個數(shù)的第j位相乘所得的數(shù)，一定是要累加到結(jié)果的第i+j位上。這里i, j都是從右往左，從0開始數(shù)。計算的過程基本上和小學生列豎式做

22、乘法相同。為編程方便，并不急于處理進位，而將進位問題留待最后統(tǒng)一處理。現(xiàn)以 83549為例來說明程序的計算過程。先算8359。59得到45個1，39得到27個10，89得到72個100。由于不急于處理進位，所以8359算完后，aResult如下：接下來算45。此處45的結(jié)果代表20個10，因此要 aResult1+=20，變?yōu)椋涸傧聛硭?3。此處43的結(jié)果代表12個100，因此要 aResult2+= 12，變?yōu)椋鹤詈笏?48。此處48的結(jié)果代表 32個1000，因此要 aResult3+= 32，變?yōu)椋撼朔ㄟ^程完畢。接下來從 aResult0開始向高位逐位處理進位問題。aResult0留下5

23、，把4加到aResult1上，aResult1變?yōu)?1后，應留下1，把5加到aResult2上最終使得aResult里的每個元素都是1位數(shù)，結(jié)果就算出來了：#include #include #define MAX_LEN 200unsigned an1MAX_LEN+10;unsigned an2MAX_LEN+10;unsigned aResultMAX_LEN * 2 + 10;char szLine1MAX_LEN+10;char szLine2MAX_LEN+10;int main()gets( szLine1); /gets函數(shù)讀取一行g(shù)ets( szLine2);int i, j

24、;int nLen1 = strlen( szLine1);memset( an1, 0, sizeof(an1);memset( an2, 0, sizeof(an2);memset( aResult, 0, sizeof(aResult);j = 0;for( i = nLen1 - 1;i = 0 ; i -)an1j+ = szLine1i - 0;int nLen2 = strlen(szLine2);j = 0;for( i = nLen2 - 1;i = 0 ; i -)an2j+ = szLine2i - 0;/每一輪都用an2的一位，去和an1各位相乘，從an1的個位開始fo

25、r( i = 0;i nLen2; i + ) /用選定的an2的那一位，去乘an1的各位 for( j = 0; j nLen1; j + ) /兩數(shù)第i, j位相乘，累加到結(jié)果的第i+j位aResulti+j += an2i*an1j; /下面的循環(huán)統(tǒng)一處理進位問題int nHighestPos = 0;for( i = 0; i = 10 ) aResulti+1 += aResulti / 10;aResulti %= 10;if( aResulti ) nHighestPos = i;for( i = nHighestPos; i = 0; i - )printf(%d, aResu

26、lti);return 0;大大整數(shù)乘法的另一種思路：改進整數(shù)乘法的另一種思路：改進計算速度計算速度l選擇乘數(shù)和被乘數(shù)l長一些的操作數(shù)作為乘數(shù)A：長度為lMaxl短一些的操作數(shù)作為被乘數(shù)B：長度為lMinl令Y(Y9)是A中每一位上的最大數(shù)字， 用Y個數(shù)組，分別表示被乘數(shù)B的1倍、2倍、 Y倍：共需要8*lMin次整數(shù)加法l2B = B + Bl3B = 2B + Bll執(zhí)行A的第K位乘以B時， 令A的第K位值為X，則直接取B的X倍結(jié)果進行相加：共需要lMax次大整數(shù)加法，每次大整數(shù)加法需要lMin次整數(shù)加法l總運算量： 8*lMin+ lMax*lMin次整數(shù)加法求2個大的正整數(shù)相除的商In

27、put第1行是測試數(shù)據(jù)的組數(shù)n，每組測試數(shù)據(jù)占2行，第1行是被除數(shù)，第2行是除數(shù)。每組測試數(shù)據(jù)之間有一個空行，每行數(shù)據(jù)不超過100個字符Outputn行，每組測試數(shù)據(jù)有一行輸出是相應的整數(shù)商Sample Input3 2405337312963373359009260457742057439230496493930355595797660791082739646 2987192585318701752584429931160870372907079248971095012509790550883793197894 1000000000000000000000000000000000000000

28、0 100000000005409656775097850895687056798068970934546546575676768678435435345 1 Sample Output0 1000000000000000000000000000000 5409656775097850895687056798068970934546546575676768678435435345 例題：例題：POJPOJ27372737 大整數(shù)除法大整數(shù)除法(P165)(P165)例題：例題：POJPOJ27372737 大整數(shù)除法大整數(shù)除法(P165)(P165) 基本的思想是反復做減法，看看從被除數(shù)里最多

29、能減去多少個除數(shù)，商就是多少。一個一個減顯然太慢，如何減得更快一些呢？以7546除以23為例來看一下：開始商為0。先減去23的100倍，就是2300，發(fā)現(xiàn)夠減3次，余下646。于是商的值就增加300。然后用646減去230，發(fā)現(xiàn)夠減2次，余下186，于是商的值增加20。最后用186減去23，夠減8次，因此最終商就是328。 所以本題的核心是要寫一個大整數(shù)的減法函數(shù)，然后反復調(diào)用該函數(shù)進行減法操作。#include #include #define MAX_LEN 110int an1MAX_LEN;int an2MAX_LEN;int tmpAn2MAX_LEN;int anResultMAX

30、_LEN;char szLine1MAX_LEN;char szLine2MAX_LEN;char szNouseMAX_LEN;int Substract( int nMaxLen, int * an1, int * an2)/大整數(shù)an1減去an2。兩者最多 nMaxLen 位，an1必須不小于an2, 差放在an1里/返回差的最高非0位的位置int nStartPos = 0;for( int i = 0;i nMaxLen ; i + ) an1i -= an2i;/逐位相減if( an1i = 0; i - );if( i = 0 )return i + 1;return 0;voi

31、d ShiftLeft( int nMaxLen,int * an1, int * an2, int n)/將大整數(shù)an1左移n位，即乘以10的n次方，結(jié)果放到an2里memcpy( an2,an1,nMaxLen * sizeof(int);if( n = 0; i - )if( i - n = 0)an2i = an1i-n;elsean2i = 0;int * Max(int nMaxLen, int * an1, int * an2)/求大整數(shù)an1和an2里面大的那個/如果都是0，則返回NULLbool bBothZero = true;for( int i = nMaxLen -1

32、; i = 0 ; i - ) if( an1i an2i )return an1;else if( an1i = 0 ; i -)an1j+ = szLine1i - 0;int nLen2 = strlen(szLine2);for( j = 0, i = nLen2 - 1;i = 0 ; i -)an2j+ = szLine2i - 0;int nHighestPos = 0;memset(anResult,0,sizeof(anResult);int nShiftLen = Length(MAX_LEN,an1) - Length(MAX_LEN,an2);/只要an1大于an2，就

33、不停相減while( Max(MAX_LEN,an1,an2) = an1 ) /算出an2的10的nShiftLen次方倍ShiftLeft(MAX_LEN, an2, tmpAn2,nShiftLen);/重復減去an2的10的nShiftLen次方倍，看能減幾次while( Max(MAX_LEN,an1,tmpAn2) = an1) Substract(MAX_LEN, an1,tmpAn2);/記錄商對應位anResultnShiftLen +;/記錄結(jié)果最高位的位置if( nHighestPos = 0 & anResultnShiftLen)nHighestPos = n

34、ShiftLen;nShiftLen -;for( i = nHighestPos; i = 0; i - ) printf(%d, anResulti);printf(n); return 0;大大整數(shù)除法的另一種思路：改進整數(shù)除法的另一種思路：改進計算速度，計算速度，以以139835除以除以23為例為例l計算23的1倍、2倍、9倍23466992115138161184207l129835除以23的最高位：執(zhí)行一次大整數(shù)減法13的最高位比上述9個數(shù)字的最高位都小139的最高位等于138的最高位l計算1835除以23：執(zhí)行兩次大整數(shù)減法183的最高位等于184的最高位相減后發(fā)現(xiàn)183小于18

35、4于是執(zhí)行183減去161POJPOJ1952:1952:浮點數(shù)求高精度冪浮點數(shù)求高精度冪描述 有一個實數(shù) R ( 0.0 R 99.999 ) ,要求寫程序精確計算 R 的 n 次方。n 是整數(shù)并且 0 n = 25。 輸入 T輸入包括多組 R 和 n。 R 的值占第 1 到 第 6 列, n 的值占第 8 和第 9 列。輸出 對于每組輸入，要求輸出一行，該行包含精確的 R 的 n 次方。輸出需要去掉前導的 0 后后面不不要的 0 。如果輸出是整數(shù)，不要輸出小數(shù)點。 樣例輸入 95.123 12 0.4321 20 5.1234 15 6.7592 9 98.999 10 1.0100 12

36、 樣例輸出 548815620517731830194541.899025343415715973535967221869852721 .00000005148554641076956121994511276767154838481760200726351203835429763013462401 43992025569.928573701266488041146654993318703707511666295476720493953024 29448126.764121021618164430206909037173276672 90429072743629540498.1075960194

37、56651774561044010001 1.126825030131969720661201 基本思路就是將浮點數(shù)當做整數(shù)進行運算，最后補上小數(shù)點。#include #include #include #include using namespace std;#define MAX_LEN 500unsigned an1MAX_LEN * 2 +10;unsigned an2MAX_LEN+10;unsigned aResultMAX_LEN * 2 + 10;int Multiply( unsigned * a1,int nLen1, unsigned * a2, int nLen2, u

38、nsigned * ar)/ ar = a1 * a2, a1長度nLen1, a2 長度nLen2int i,j;memset( ar, 0, sizeof(aResult);for( i = 0;i nLen2; i + ) /每一輪都用a1的一位，去和a2各位相乘,從a1的個位開始for( j = 0; j nLen1; j + ) /用選定的a1的那一位，去乘 /a2的各位 ari+j += a2i*a1j; /兩數(shù)第i, j位相乘，累加到結(jié) /果的第i+j位int nLen = 0;/下面的循環(huán)統(tǒng)一處理進位問題for( i = 0; i = 10 ) ari+1 += ari / 1

39、0;ari %= 10;if( ari )nLen = i + 1;return nLen;int main()char R30; int n;int nBits; /R小數(shù)點后面的位數(shù)int i;while( scanf(%s%d ,R,&n)!= EOF) int nLen = strlen(R);int j = 0;nBits = 0;/乘數(shù)小數(shù)點后面位數(shù)memset(an1,0,sizeof(an1);memset(an2,0,sizeof(an2);bool bDecMeet = false; /是否碰到小數(shù)點了bool bNoneZeroMeet = false; /是否碰

40、到非0位了/下面把乘數(shù)變成高精度表示形式，并算小數(shù)點后位數(shù)for( i = nLen - 1; i = 0; i- ) if( Ri = .) bNoneZeroMeet = true;bDecMeet = true;else if( Ri != 0 ) bNoneZeroMeet = true;if( bNoneZeroMeet) an1j+ = Ri - 0;if(!bDecMeet) nBits +;if( !bDecMeet)nBits = 0;int nLen2;if( bDecMeet) if( nBits )nLen2 = nLen - 1;else nLen2 = strchr

41、(R,.) - R;else nLen2 = nLen;int nLen1 = nLen2; /結(jié)果長度memcpy(an2,an1,sizeof(an2);memcpy(aResult,an1,sizeof(an1);for( i = 0; i n - 1;i + ) nLen1 = Multiply(an1,nLen1, an2,nLen2, aResult);memcpy( an1,aResult, sizeof(aResult);int nTotalBits = nBits * n ; /結(jié)果的小數(shù)點后面的位數(shù)/下面輸出結(jié)果if( nLen1 = 0) /結(jié)果就是0printf(0);

42、else if( nLen1 = nTotalBits) /結(jié)果小于1 printf(.);int i;for( i = 0;i =0; i -)printf(%d,aResulti);else for( int i = nLen1-1; i =0; i -) printf(%d,aResulti);if( nTotalBits & i = nTotalBits)printf(.);printf(n); return 0; 問題描述問題描述形如2p-1的素數(shù)稱為麥森數(shù)，這時P一定也是個素數(shù)。但反過來不一定，即如果P是個素數(shù)。2p-1不一定也是素數(shù)。到1998年底，人們已找到了37個麥森

43、數(shù)。最大的一個是P=3021377，它有909526位。麥森數(shù)有許多重要應用，它與完全數(shù)密切相關(guān)。 你的任務：輸入P (1000P3100000) , 計算2p-1的位數(shù)和最后500位數(shù)字（用十進制高精度數(shù)表示）輸入數(shù)據(jù)輸入數(shù)據(jù)只包含一個整數(shù)P(1000P3100000)輸出要求輸出要求第1行：十進制高精度數(shù)2p-1的位數(shù)。 第2-11行：十進制高精度數(shù)2p-1的最后500位數(shù)字。（每行輸出50位，共輸出10行，不足500位時高位補0） 不必驗證2p-1與P是否為素數(shù)POJ2706POJ2706: :麥森數(shù)麥森數(shù)輸入樣例輸入樣例1279輸出樣例輸出樣例386000000000000000000

44、000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000104079321946643990819252403273640855386152622472667048053191123504036080596733602980122394417323241848424216139542810077913835662483234649081399066056773207629241295093892203457731833496615835504729594205

45、47689811211693677147548478866962501384438260291732348885311160828538416585028255604666224831890918801847068222203140521026698435488732958028878050869736186900714720710555703168729087基本思路基本思路第一個問題，輸出2p-1有多少位。由于2p的個位數(shù)只可能是2, 4, 6, 8所以2p-1和2p的位數(shù)相同。使用C/C+標準庫中在math.h里聲明的，求以10為底的對數(shù)的函數(shù)double log10(double x)

46、 函數(shù)，就能輕松求得2p-1的位數(shù)。求2p,如果每次乘以2,那么一共要乘 P0，考慮p的二進制形式，則不難得到：p = a020 +a121+ a222+ an-12n-1 + 2n這里，ai要么是1，要么是0。因而：。 在前面的高精度計算中，我們用數(shù)組來存放大整數(shù)，數(shù)組的一個元素對應于十進制大整數(shù)的一位。本題如果也這樣做，就會超時。為了加快計算速度，可以用一個數(shù)組元素對應于大整數(shù)的4位，即將大整數(shù)表示為10000進制，而數(shù)組中的每一個元素就存放10000進制數(shù)的1位。例如，用int型數(shù)組 a來存放整數(shù)6373384，那么只需兩個數(shù)組元素就可以了，a0=3384, a1=637。由于只要求結(jié)果

47、的最后500位數(shù)字，所以我們不需要計算完整的結(jié)果，只需算出最后500位即可。因為用每個數(shù)組元素存放十進制大整數(shù)的4位，所以本題中的數(shù)組最多只需要125個元素。#include #include #define LEN 125 /每數(shù)組元素存放十進制的4位，因此數(shù)組最多只要125個元素即可。#include /* Multiply 函數(shù)功能是計算高精度乘法 a * b結(jié)果的末500位放在a中 */void Multiply(int* a, int* b) int i, j; int nCarry; /存放進位int nTmp;int cLEN; /存放結(jié)果的末500位memset(c, 0, s

48、izeof(int) * LEN);for (i=0;iLEN;i+)nCarry=0; for (j=0;jLEN-i;j+)nTmp=ci+j+aj*bi+nCarry;ci+j=nTmp%10000;nCarry=nTmp/10000; memcpy( a, c, LEN*sizeof(int); int main()int i;int p;int anPowLEN; /存放不斷增長的2的次冪int aResultLEN; /存放最終結(jié)果的末500位scanf(%d, & p);printf(%dn, (int)(p*log10(2)+1); /下面將2的次冪初始化為2(20)(

49、ab表示a的b次方)， / 最終結(jié)果初始化為1anPow0=2; aResult0=1; for (i=1;i0) / p = 0 則說明p中的有效位都用過了，不需再算下去if ( p & 1 ) /判斷此時p中最低位是否為1Multiply(aResult, anPow); p=1; Multiply(anPow, anPow);aResult0-; /2的p次方算出后減1 /輸出結(jié)果for (i=LEN-1;i=0;i-) if (i%25=12)printf(%02dn%02d, aResulti/100, aResulti%100);elseprintf(%04d, aResulti);if (i%25=0)printf(n);return 0;例題：例題：POJPOJ29522952 循環(huán)數(shù)循環(huán)數(shù) l問題描述l當一個N位的整數(shù)X滿足下列條件時，稱其為循環(huán)數(shù)：X與任意一個整數(shù)1Y N相乘時，都將產(chǎn)生一個X的“循環(huán)”。即：分別將這兩個整數(shù)的第1位數(shù)字與最后1位數(shù)字連在一起，可以得到一個相同的數(shù)字循環(huán)；當然兩個整數(shù)在該數(shù)字循環(huán)中的起始位置不同。例如，142857是一個循