ACM高精度计算

1、第九讲第九讲ACMACM算法与程序设计算法与程序设计2大整数加法大整数加法1、链接地址、链接地址 http:/ 位的非负整数的和。位的非负整数的和。输入数据输入数据有两行，每行是一个不超过有两行，每行是一个不超过200 位的非负整数，位的非负整数，没有多余的前导没有多余的前导0。3问题描述问题描述输出要求输出要求一行，即相加后的结果。结果里不能有多余的前导一行，即相加后的结果。结果里不能有多余的前导0，即如果结果是即如果结果是342，那么就不能，那么就不能输出为输出为0342。输入样例输入样例2222222222222222222233333333333333333333输出样例输出样例Out

2、put Sample:555555555555555555554n 首先要解决的就是存储首先要解决的就是存储200 位整数的问题。显然，任何位整数的问题。显然，任何C/C+固有类型的变量都无法保存它。最直观的想法是可以用一个字符固有类型的变量都无法保存它。最直观的想法是可以用一个字符串来保存它。字符串本质上就是一个字符数组，因此为了编程更串来保存它。字符串本质上就是一个字符数组，因此为了编程更方便，我们也可以用数组方便，我们也可以用数组unsigned an200来保存一个来保存一个200 位位的整数，让的整数，让an0存放个位数，存放个位数，an1存放十位数，存放十位数，an2存放百存放百位

3、数位数n 那么如何实现两个大整数相加呢？方法很简单，就是模拟小学那么如何实现两个大整数相加呢？方法很简单，就是模拟小学生列竖式做加法，从个位开始逐位相加，超过或达到生列竖式做加法，从个位开始逐位相加，超过或达到10 则进位。则进位。也就是说，用也就是说，用unsigned an1201保存第一个数，用保存第一个数，用unsigned an2200表示第二个数，然后逐位相加，相加的结果直接存放在表示第二个数，然后逐位相加，相加的结果直接存放在an1 中。要注意处理进位。另外，中。要注意处理进位。另外，an1 数组长度定为数组长度定为201，是因，是因为两个为两个200 位整数相加，结果可能会有位

4、整数相加，结果可能会有201 位。位。n 实际编程时，不一定要费心思去把数组大小定得正好合适，稍实际编程时，不一定要费心思去把数组大小定得正好合适，稍微开大点也无所谓，以免不小心没有算准这个微开大点也无所谓，以免不小心没有算准这个“正好合适正好合适”的数的数值，而导致数组小了，产生越界错误。值，而导致数组小了，产生越界错误。3、解题思路、解题思路54、参考程序、参考程序#include #include #define MAX_LEN 200int an1MAX_LEN+10;int an2MAX_LEN+10;char szLine1MAX_LEN+10;char szLine2MAX_LE

5、N+10;int main(void) scanf(%s, szLine1); scanf(%s, szLine2); int i, j; memset( an1, 0, sizeof(an1); memset( an2, 0, sizeof(an2);64、参考程序、参考程序 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 = 0 ; i -) a

6、n2j+ = szLine2i - 0; for( i = 0;i = 10 ) /看是否要进位看是否要进位 an1i -= 10; an1i+1 +; /进位进位 for( i = MAX_LEN; (i = 0) & (an1i = 0); i - ) ; if(i=0) for( ; i = 0; i-) printf(%d, an1i); else printf(0); return 0;7大整数乘法大整数乘法1、链接地址、链接地址 http:/ 位的非负整数的积。输入数据位的非负整数的积。输入数据有两行，每行是一个不超过有两行，每行是一个不超过200 位的非负整数，位的非负整数，没有

7、多余的前导没有多余的前导0。输出要求一行，即相乘后的结。输出要求一行，即相乘后的结果。结果里不能有多余的前导果。结果里不能有多余的前导0，即如果结果是，即如果结果是342，那么就不能输出为，那么就不能输出为0342。8问题描述问题描述n 输入样例输入样例 12345678900 98765432100n 输出样例输出样例 12193263111263526900009n 在程序中，用在程序中，用unsigned an1200和和unsigned an2200分别存放两个乘数，用分别存放两个乘数，用aResult400来来存放积。计算的中间结果也都存在存放积。计算的中间结果也都存在aResult

8、中。中。aResult长度取长度取400是因为两个是因为两个200 位的数相乘，位的数相乘，积最多会有积最多会有400 位。位。an10, an20, aResult0都表示个位。都表示个位。n计算的过程基本上和小学生列竖式做乘法相同。计算的过程基本上和小学生列竖式做乘法相同。为编程方便，并不急于处理进位，而将进位问题留为编程方便，并不急于处理进位，而将进位问题留待最后统一处理。待最后统一处理。n现以现以 83549 为例来说明程序的计算过程。为例来说明程序的计算过程。3、解题思路、解题思路10先算先算8359。59 得到得到45 个个1，39 得到得到27 个个10，89 得得到到72 个个

9、100。由于不急于处理进位，所以。由于不急于处理进位，所以8359 算完后，结算完后，结果如下：果如下：3、解题思路、解题思路接下来算接下来算45。此处。此处45 的结果代表的结果代表20 个个10，因此要，因此要 c1+=20，变为：，变为：再下来算再下来算43。此处。此处43 的结果代表的结果代表12 个个100，因此要，因此要 c2+= 12，变为：，变为：113、解题思路、解题思路最后算最后算 48。此处。此处48 的结果代表的结果代表 32 个个1000，因此要，因此要 c3+= 32，变为：，变为：乘法过程完毕。接下来从乘法过程完毕。接下来从 c0开始向高位逐位处理进位问题。开始向

10、高位逐位处理进位问题。c0留下留下5，把，把4 加到加到c1上，上，c1变为变为51 后，应留下后，应留下1，把，把5 加到加到c2上上最终使得最终使得c 里的每个元素都是里的每个元素都是1 位数，结果就位数，结果就算出来了：算出来了：规律：一个数的第规律：一个数的第i 位和另一个数的第位和另一个数的第j 位相乘所得的数，一位相乘所得的数，一定是要累加到结果的第定是要累加到结果的第i+j 位上。这里位上。这里i, j 都是从右往左，从都是从右往左，从0 开始数。开始数。124、参考程序、参考程序#include #include #define MAX_LEN 200int main(void

11、) int i, j; int len1,len2; int aMAX_LEN+10,bMAX_LEN+10,cMAX_LEN*2+10; char str1MAX_LEN+10,str2MAX_LEN+10; for(i=0;iMAX_LEN+10;i+) ai=bi=0; for(i=0;i=0; i-)/把数字倒过来把数字倒过来 aj+=str1i-0; len2=strlen(str2); for(j=0,i=len2-1; i=0; i-)/倒转第二个整数倒转第二个整数 bj+=str2i-0;134、参考程序、参考程序 for(i=0; ilen2; i+)/用第二个数乘以第一个数

12、用第二个数乘以第一个数,每次一位每次一位 for(j=0; jlen1; j+) ci+j+= bi*aj; /先乘起来先乘起来,后面统一进位后面统一进位 for(i=0; i=10) ci+1+=ci/10; ci%=10; for(i=MAX_LEN*2; (ci=0)&(i=0); i-);/跳过高位的跳过高位的0 if(i=0) for(;i=0;i-) printf(%d, ci); else printf(0); return 0;14大整数除法大整数除法1、链接地址、链接地址 http:/ 求两个大的正整数相除的商求两个大的正整数相除的商 输入数据输入数据 第第1 行是测试数据的

13、组数行是测试数据的组数n，每组测试数据占，每组测试数据占2 行，第行，第1 行是被除数，第行是被除数，第2 行是除数。每组测试数行是除数。每组测试数据之间有一个空行，每行数据不超过据之间有一个空行，每行数据不超过100 个字符个字符 输出要求输出要求 n 行，每组测试数据有一行输出是相应的整数行，每组测试数据有一行输出是相应的整数商商15问题描述问题描述输入样例输入样例324053373129633733590092604577420574392304964939303555957976607910827396462987192585318701752584429931160870372907

14、079248971095012509790550883793197894100000000000000000000000000000000000000001000000000054096567750978508956870567980689709345465465756767686784354353451输出样例输出样例01000000000000000000000000000000540965677509785089568705679806897093454654657567676867843543534516n 基本的思想是反复做减法，看看从被除数里最多能减去多基本的思想是反复做减法，看看

15、从被除数里最多能减去多少个除数，商就是多少。一个一个减显然太慢，如何减得更少个除数，商就是多少。一个一个减显然太慢，如何减得更快一些呢？以快一些呢？以7546 除以除以23 为例来看一下：开始商为为例来看一下：开始商为0。先。先减去减去23 的的100 倍，就是倍，就是2300，发现够减，发现够减3 次，余下次，余下646。于是商的值就增加于是商的值就增加300。然后用。然后用646 减去减去230，发现够减，发现够减2 次，余下次，余下186，于是商的值增加，于是商的值增加20。最后用。最后用186 减去减去23，够减够减8 次次，因此最终商就是因此最终商就是328。n 所以本题的核心是要写

16、一个大整数的减法函数，然后反复所以本题的核心是要写一个大整数的减法函数，然后反复调用该函数进行减法操作。调用该函数进行减法操作。 计算除数的计算除数的10 倍、倍、100 倍的时倍的时候，不用做乘法，直接在除数后面补候，不用做乘法，直接在除数后面补0 即可。即可。3、解题思路、解题思路174、参考程序、参考程序n#include n#include n#define MAX_LEN 200nchar szLine1MAX_LEN + 10;nchar szLine2MAX_LEN + 10;nint an1MAX_LEN + 10; /被除数被除数, an10对应于个位对应于个位nint an

17、2MAX_LEN + 10; /除数除数, an20对应于个位对应于个位nint aResultMAX_LEN + 10; /存放商，存放商，aResult0对应于个位对应于个位n/长度为长度为 nLen1 的大整数的大整数p1 减去长度为减去长度为nLen2 的大整数的大整数p2n/结果放在结果放在p1 里，返回值代表结果的长度里，返回值代表结果的长度n/如不够减返回如不够减返回-1，正好减完返回，正好减完返回 0nint Substract( int * p1, int * p2, int nLen1, int nLen2)nn int i;n if( nLen1 =0; i - ) n

18、n if( p1i p2i ) break; /p1p2n else if( p1i p2i ) return -1; /p1p2n n n for( i = 0; i =nLen2 时，时，p2i 0n p1i -= p2i; n if( p1i = 0 ; i- )n if( p1i )/找到最高位第一个不为找到最高位第一个不为0n return i + 1;n return 0;/全部为全部为0，说明两者相等，说明两者相等n194、参考程序、参考程序nint main()nn int t, n;n scanf(%d, &n);n for( t = 0; t = 0 ; i -)n an1

19、j+ = szLine1i - 0;n int nLen2 = strlen(szLine2);n for( j = 0, i = nLen2 - 1;i = 0 ; i -)n an2j+ = szLine2i - 0;n if( nLen1 0)n n for( i = nLen1 -1; i = nTimes; i - ) n an2i = an2i-nTimes;/朝高位移动朝高位移动n for( ; i = 0; i-)/低位补低位补0n an2i = 0;n nLen2 = nLen1;n n for( j = 0 ; j = 0) n n nLen1 = nTmp;n aResu

20、ltnTimes-j+; /每成功减一次，则将商的相应位加每成功减一次，则将商的相应位加1n n 214、参考程序、参考程序n /下面输出结果，先跳过高位下面输出结果，先跳过高位0n for( i = MAX_LEN ; (i = 0) & (aResulti = 0); i - );n if( i = 0)n for( ; i=0; i-)n printf(%d, aResulti);n elsen printf(0);n printf(n);n n return 0;n22麦森数麦森数1、链接地址、链接地址 http:/ 形如形如2P-1 的素数称为麦森数，这时的素数称为麦森数，这时P 一

21、定也是一定也是个素数。但反过来不一定，即如果个素数。但反过来不一定，即如果P 是个素数。是个素数。2P-1 不一定也是素数。麦森数有许多重要应用，它与完不一定也是素数。麦森数有许多重要应用，它与完全数全数完全数完全数(又称完备数，是一些特殊的自然数。它所又称完备数，是一些特殊的自然数。它所有的真因子（即除了自身以外的约数）的和恰好等于有的真因子（即除了自身以外的约数）的和恰好等于它本身。它本身。)密切相关密切相关. 你的任务：输入你的任务：输入P (1000P3100000) , 计算计算2p-1 的位数和最后的位数和最后500 位数字（用十进制高精度数表位数字（用十进制高精度数表示）示）23

22、问题描述问题描述输入数据输入数据只包含一个整数只包含一个整数P(1000P0，考虑，考虑p 的二进制形式，则不难得到：的二进制形式，则不难得到：n这里，这里，ai 要么是要么是1，要么是，要么是0。3、解题思路、解题思路0121012122222nnnpaaaa 26n 因而：因而：n 计算计算2p 的办法就是：先将结果的值设为的办法就是：先将结果的值设为1，计算，计算21。如果。如果a0 值为值为1，则结果乘以，则结果乘以21；计算；计算22，如果，如果a1 为为1，则结果乘以，则结果乘以22；计算；计算24，如果，如果a2 为为1，则，则结果乘以结果乘以24；总之，第总之，第i 步步(i

23、从从0 到到n，an 是是1)就计算就计算22i，如果，如果ai 为为1，则结果就乘以，则结果就乘以22i。每次。每次由由22i22i就能算出就能算出22(i+1)。由于。由于p可能很大，所可能很大，所以上面的乘法都应该使用高精度计算。由于题目只以上面的乘法都应该使用高精度计算。由于题目只要求输出要求输出500 位，所以这些乘法都是只须算出末尾位，所以这些乘法都是只须算出末尾的的500 即可。即可。3、解题思路、解题思路101122242222222nnnaaaap 27n在前面的高精度计算中，我们用数组来存放大整在前面的高精度计算中，我们用数组来存放大整数，数组的一个元素对应于十进制大整数的

24、一位。数，数组的一个元素对应于十进制大整数的一位。本题如果也这样做，就会超时。为了加快计算速度，本题如果也这样做，就会超时。为了加快计算速度，可以用一个数组元素对应于大整数的可以用一个数组元素对应于大整数的4 位，即将大位，即将大整数表示为整数表示为10000 进制，而数组中的每一个元素就进制，而数组中的每一个元素就存放存放10000 进制数的进制数的1 位。例如，用位。例如，用int 型数组型数组 a 来存放整数来存放整数6373384，那么只需两个数组元素就可，那么只需两个数组元素就可以了，以了，a0=3384, a1=637。n由于只要求结果的最后由于只要求结果的最后500 位数字，所以

25、我们不位数字，所以我们不需要计算完整的结果，只需算出最后需要计算完整的结果，只需算出最后500 位即可。位即可。因为用每个数组元素存放十进制大整数的因为用每个数组元素存放十进制大整数的4 位，所位，所以本题中的数组最多只需要以本题中的数组最多只需要125 个元素。个元素。3、解题思路、解题思路284、参考程序、参考程序n#include n#include n#define LEN 125 /每数组元素存放每数组元素存放4 位，数组最多需要位，数组最多需要125 个元素个元素n#include n/计算高精度乘法计算高精度乘法 a * b, 结果的末结果的末500 位放在位放在a 中中nvoi

26、d Multiply(int* a, int* b)nn int i, j;n int nCarry; /存放进位存放进位n int nTmp;n int cLEN; /存放结果的末存放结果的末500 位位n memset(c, 0, sizeof(int) * LEN);n for (i=0;iLEN;i+) n n nCarry=0;n for (j=0;jLEN-i;j+) n n nTmp=ci+j+aj*bi+nCarry;n ci+j=nTmp%10000;n nCarry=nTmp/10000;n n n memcpy( a, c, LEN*sizeof(int);n294、参考

27、程序、参考程序nint main(void)nn int i;n int p;n int anPowLEN; /存放不断增长的存放不断增长的2 的次幂的次幂n int aResultLEN; /存放最终结果的末存放最终结果的末500 位位n scanf(%d, & p);n printf(“%dn”, (int)(p*log10(2.0)+1);n /下面将下面将2 的次幂初始化为的次幂初始化为2(20)(ab 表示表示a 的的b 次方次方)，n / 最终结果初始化为最终结果初始化为1n anPow0=2;n aResult0=1;n for (i=1;i0) /下面计算下面计算2 的的p 次

28、方次方n / p = 0 则说明则说明p 中的有效位都用过了，不需再算下去中的有效位都用过了，不需再算下去n if ( p & 1 ) /判断此时判断此时p 中最低位是否为中最低位是否为1n Multiply(aResult, anPow);n p=1;n Multiply(anPow, anPow);n 304、参考程序、参考程序n aResult0-; /2p-1n /输出结果输出结果n for (i=LEN-1;i=0;i-) n n if (i%25=12)n printf(%02dn%02d, aResulti/100,n aResulti%100);n else n n print

29、f(%04d, aResulti);n if (i%25=0)n printf(n);n n n return 0;n31练习：练习：ExponentiationDescription (POJ：1001)Problems involving the computation of exact values of very large magnitude and precision are common. For example, the computation of the national debt is a taxing experience for many computer systems. This problem requires that you write a progra