C语言程序设计100例之（69）：麦森数
例69 麦森数
问题描述
形如2p-1的素数称为麦森数，这时P一定也是个素数。但反过来不一定，即如果P是个素数。2p-1不一定也是素数。到1998年底，人们已找到了37个麦森数。最大的一个是P=3021377，它有909526位。麦森数有许多重要应用，它与完全数密切相关。
任务：从文件中输入P (1000
输入
文件中只包含一个整数P(1000 输出 第1行：十进制高精度数2p-1的位数。 第2-11行：十进制高精度数2p-1的最后500位数字。（每行输出50位，共输出10行，不足500位时高位补0） 不必验证2p-1与P是否为素数。 输入样例 1279 输出样例 386 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000104079321946643990819252403273640855 38615262247266704805319112350403608059673360298012 23944173232418484242161395428100779138356624832346 49081399066056773207629241295093892203457731833496 61583550472959420547689811211693677147548478866962 50138443826029173234888531116082853841658502825560 46662248318909188018470682222031405210266984354887 32958028878050869736186900714720710555703168729087 由于2p的个位数字只可能是2、4、6、8，所以2p-1 和2p的位数相同。利用表达式(int)(p*log10(2))+1)可以轻松求得2p-1 的位数。 2p 的计算采用快速幂运算来完成。关于快速幂运算请参考前文“”（https://www.cnblogs.com/cs-whut/p/15757118.html）。 由于P值较大，快速幂运算中的乘法都应该使用高精度计算。由于题目只要求输出后面的500位，所以乘法只须算出末尾的500位即可。 为了加快计算速度，采用万进制表示一个大整数，即用一个数组元素来保存大整数的4 位。例如，用int 型数组a来存放大整数1234567890，那么只需3个数组元素就可以了， a[0]=7890，a[1]=3456，a[2]=12。 #include #include #include #define LEN 125 // 采用万进制，因此保存500位只要125个数组元素 void multiply(int *a, int *b) { int c[LEN]; memset(c, 0, sizeof(c)); int i, j; int carry,tmp; for (i=0;i { carry=0; for (j=0;j { tmp=c[i+j]+a[j]*b[i]+carry; c[i+j]=tmp%10000; carry=tmp/10000; } } for (i=0;i a[i]=c[i]; } int main() { int i,p; int p2m[LEN]; // 存放不断增长的2的m次幂 int ans[LEN]; scanf("%d", &p); printf("%d\n", (int)(p*log10(2))+1); memset(p2m, 0, sizeof(p2m)); memset(ans, 0, sizeof(ans)); p2m[0]=2; ans[0]=1; while (p>0) // 采用快速幂运算计算2的p次方 { if ( p & 1 ) multiply(ans, p2m); p>>=1; multiply(p2m, p2m); } ans[0]--; for (i=LEN-1;i>=0;i--) { if (i%25==12) printf("%02d\n%02d", ans[i]/100,ans[i]%100); else { printf("%04d", ans[i]); if (i%25==0) printf("\n"); } } return 0; } 问题描述 给定正整数N和M（5 ≤ M ≤ N ≤ 100)，计算 的值。 输入 输入包括若干组测试用例，每组测试用例占1行，包含两个正整数N和M，0 0表示输入结束。 输出 输出对应的C值，并按如下格式输出：[N] things taken [M] at a time is [C] exactly. 输入样例 100 6 20 5 18 6 0 0 输出样例 100 things taken 6 at a time is 1192052400 exactly. 20 things taken 5 at a time is 15504 exactly. 18 things taken 6 at a time is 18564 exactly. （1）编程思路。 组合数C(M, N)可化简为N*(N-1)*…*(N-M+1) /(M*(M-1)*…*2*1)，因此本题实际是一个大整数和普通整数进行乘法运算，一个大整数和普通整数进行除法运算两种操作。 定义全局数组int a[200]保存所求的组合数，全局变量len保存所求组合数的位数。初始时，a[0]=1，len=1。 编写函数void mul(int b)完成大整数a与整数b相乘，乘积仍保存在数组a中，函数void div(int b)完成大整数a除以整数b，商也保存在数组a中。 （2）源程序。 #include int a[200]; int len = 0; // len保存高精度数当前的位数 void mul(int b) // 高精度乘法，a为被乘数，b为乘数 { int i,cf=0; for (i=0; i<200; i++) { a[i] = a[i]*b+cf; cf = a[i]/10; a[i]%= 10; } for (i=len; i<200; i++) // 更新位数len if(a[i] != 0) len++; } void div(int b) // 高精度除法，a为被除数，b为除数 { int last = 0; // 余数 int i; for (i=len-1; i>=0; i--) { int cur = last*10+a[i]; if (cur { a[i] = 0; // 将商还是保存在被除数数组a中 last = cur; } else { a[i] = cur/b; last = cur%b; } } for (i=len-1; i>=0; i--) // 更新位数len if (a[i]!=0) break; len=i+1; } int main() { int n, m; while (scanf("%d%d", &n, &m) && (n||m)) { int i; for (i=0; i<200; i++) a[i] = 0; a[0] = len = 1; for (i=n-m+1; i <= n; i++) mul(i); for (i=2; i<=m; i++) div(i); printf("%d things taken %d at a time is ", n, m); for (i=len-1; i>=0; i--) printf("%d", a[i]); printf(" exactly.\n"); } return 0; } 问题描述 给定一个基数b和两个非负的基数b整数p和m，计算p mod m并将结果打印为基数b整数。p mod m被定义为最小的非负整数k，对于某个整数a，p=a*m+k。 输入 输入包含多组测试用例。每组测试用例占一行，包含三个无符号整数。第一个数b是介于2和10之间的十进制数。第二个p最多包含1000个介于0和b-1之间的数字。第三个数字m最多包含9个介于0和b-1之间的数字。最后一行为一个0，表示输入的结束。 输出 对于每个测试用例，输出一行，为p mod m的Base-b整数。 输入样例 2 1100 101 10 123456789123456789123456789 1000 输出样例 10 789 （1）编程思路。 由于被除数p可能有1000位，因此定义字符数组char p[1001]来保存被除数，除数m最多9位，由于输入的是b进制数，为方便转换为10进制整数，也用字符数组char m[10]来保存。输入结束后，将m按权值展开转换为10进制整数d，之后进行大整数p除以整数d的10进制除法运算，求得余数last，余数是一个不超过9位数的10进制整数，最后将其按除b取余的方法转换为b进制整数输出。 （2）源程序。 #include int main() { int b; while (scanf("%d", &b) && b) { char p[1001],m[10]; scanf("%s %s",p,m); int i,d=0; for (i=0; m[i]!='\0'; i++) d=d*b+m[i]-'0'; int last = 0; // 余数 for (i=0; p[i]!='\0'; i++) { int cur = last*b+p[i]-'0'; last = cur%d; } int len=0,a[10]; do { a[len++]=last%b; last/=b; } while (last!=0); for (i=len-1; i>=0; i--) printf("%d", a[i]); printf("\n"); } return 0; } 问题描述 Sheng bill 有着惊人的心算能力，甚至能用大脑计算出两个巨大的数的最大公约数！因此他经常和别人比赛计算最大公约数。有一天Sheng bill很嚣张地找到了你，并要求和你比赛，但是输给 Sheng bill 岂不是很丢脸！所以你决定写一个程序来教训他。 输入 共两行，第一行一个整数a，第二行一个整数 b（0 输出 一行，表示a和b的最大公约数。 输入样例 12 54 输出样例 （1）编程思路1。 利用转辗相除法可以求两个整数的最大公约数。例如求两个整数a和b的最大公约数可以写成如下的循环： r=a%b; while(r!=0) { a = b; b = r; r=a%b; } 循环结束后，整数b的值就是所求的最大公约数。 由于题目中是求两个巨大的整数的最大公约数，因此需要采用高精度运算。 将大整数用字符串保存，编写函数void mod(char *a,char *b,char *r)实现r=a%b。 实现大整数除法的基本的思想是反复做减法，从被除数里最多能减去多少个除数，商就是多少，最后剩下的不够减的部分就是余数。但是不能一个一个地减除数，这样既慢又不好处理。 实际处理方法应该这样，将除数扩大10倍、100倍、…或10k倍，使得除数和被除数等长，之后再进行减法操作，依次减除数的10k倍、…、除数的100倍、除数的10倍、除数本身。每次记下够减的次数，所得结果就是商，所有相减完成后，被除数的剩余部分就是所求的余数。 下面以231708除以328为例进行说明。 先将除数328扩大1000倍，即后面加上3个0，使得除数328000与被除数231708等长，231708减去328000，不够减，因此记下减的次数为0；之后，去掉除数后面的1个0，得到32800（即除数扩大100倍），231708减去32800，够减7次，余下 2108，同样记下减的次数为7；再去掉除数后面的1个0，得到3280（即除数扩大10倍），2108减3280，不够减，同样记下减的次数为0；再去掉除数后面的1个0，此时就是除数本身328，2108减328，够减6次，余下140，同样记下减的次数为6，结束运算。依次记下的减的次数为0706，去掉前导的0，商就是706，余数就是140。 （2）源程序1。 #include #include #define MAXN 10100 void sub(char *a,char *b,char *c) { int len1=strlen(a),len2=strlen(b); int x[MAXN],y[MAXN],z[MAXN]; int len=len1; memset(x,0,sizeof(x)); memset(y,0,sizeof(y)); memset(z,0,sizeof(z)); int i,j; for (i=len1-1,j=0;i>=0;i--,j++) x[j]=a[i]-'0'; for (i=len2-1,j=0;i>=0;i--,j++) y[j]=b[i]-'0'; int cf=0; for (i=0;i { z[i]=x[i]-y[i]+cf; if (z[i]<0) { z[i]+=10; cf=-1; } else cf=0; } while (len>0 && z[len-1]==0) // 去前置0 len--; if (len==0) // a-b=0时特判 { c[0]='0'; c[1]='\0'; return ; } for (i=0;i c[i]=z[len-1-i]+'0'; c[len]='\0'; } int bigger(char *a,char *b) { if (strlen(a)>strlen(b)) return 1; if (strlen(a) if (strcmp(a,b)>=0) return 1; else return 0; } void mod(char *a,char *b,char *r) // r=a%b { if (bigger(a,b)==0) // 被除数a小于除数b，余数为a { strcpy(r,a); return ; } char ta[MAXN],tb[MAXN]; strcpy(ta,a); strcpy(tb,b); int len1=strlen(ta); int len2=strlen(tb); int i; for (i=len2;i tb[i]='0'; tb[i]='\0'; for (i=0;i<=len1-len2;i++) { while (bigger(ta,tb)) { sub(ta,tb,ta); } if (strlen(tb)>len2) tb[strlen(tb)-1]='\0'; if (strcmp(ta,"0")==0) break; } strcpy(r,ta); } int main() { char a[MAXN],b[MAXN],r[MAXN]; scanf("%s%s",a,b); mod(a,b,r); while (strcmp(r,"0")!=0) { strcpy(a,b); strcpy(b,r); mod(a,b,r); } printf("%s\n",b); return 0; } 将上面的源程序1提交给洛谷题库https://www.luogu.com.cn/problem/P2152，会超时，显示测评结果如下。 （3）编程思路2。 上面源程序1中处理大整数相减时，每个数组元素保存大整数的1位数字，这样既浪费存储空间，又耗费计算时间。因此提交给洛谷题库https://www.luogu.com.cn/problem/P2152，会超时。 为加快运算速度，可以将输入的两个大整数按每8位数字1组分别保存到两个整型数组a和b中。数组元素a[0]和b[0]分别保存两个整数的组数（每8位1组）。例如，大整数1234567890保存到数组a中为：a[1]=34567890，a[2]=12，a[0]=2。 按每8位数字一组的处理方式改写源程序1如下。 （4）源程序2。 #include #include #define MAXN 1255 #define BASE 100000000 #define WIDTH 8 void sub(int *a,int *b) // a=a-b { int i,j,cf=0; for (i=a[0],j=b[0];i>=1;i--,j--) { if (j>=1) a[i]=a[i]-b[j]+cf; else a[i]=a[i]+cf; if (a[i]<0) { a[i]+=BASE; cf=-1; } else cf=0; } int len=a[0]; i=1; while (len>0 && a[i]==0) // 去前置0 { i++; len--; } if (len==0) // a-b=0时特判 { a[0]=1; a[1]=0; return ; } for (j=1;i<=a[0];i++) a[j++]=a[i]; a[0]=len; } int bigger(char *a,char *b) { if (strlen(a)>strlen(b)) return 1; if (strlen(a) if (strcmp(a,b)>=0) return 1; else return 0; } int cmp(int *x,int *y) // x>=y ? { if (x[0]>y[0]) return 1; else if (x[0] else { int i; for (i=1; i<=x[0]; i++) if (x[i]>y[i]) return 1; else if (x[i] } return 1; } void mod(int *a,int *b,int *r) // r=a%b { int tb[MAXN]={0}; int i; for (i=1;i<=b[0];i++) tb[i]=b[i]; tb[0]=a[0]; // 将tb的末尾添加0到与a等长 for (i=0;i<=a[0]-b[0];i++) { while (cmp(a,tb)) { sub(a,tb); } tb[0]--; if (a[1]==0) break; } for (i=0;i<=a[0];i++) r[i]=a[i]; } void change(char s[],int a[]) { int len=strlen(s); a[0]=(len+WIDTH-1)/WIDTH; int i,k=a[0]+1,p; for (i=len-1;i>=0;i--) { if ((len-1-i)%WIDTH==0) { p=1; k--; } a[k]+=p*(s[i]-'0'); p*=10; } } void copy(int *a,int *b) { int i; memset(a,0,sizeof(int)*MAXN); for (i=0;i<=b[0];i++) a[i]=b[i]; } int main() { char s1[8*MAXN],s2[8*MAXN]; scanf("%s%s",s1,s2); int a[MAXN]={0},b[MAXN]={0}; if (bigger(s1,s2)) { change(s1,a); change(s2,b); } else { change(s2,a); change(s1,b); } int r[MAXN]; mod(a,b,r); while (r[1]!=0) { copy(a,b); copy(b,r); mod(a,b,r); } printf("%d",b[1]); int i; for (i=2;i<=b[0];i++) printf("%08d",b[i]); printf("\n"); return 0; } 再将上面的源程序2提交给洛谷题库https://www.luogu.com.cn/problem/P2152，可以Accepted。 （1）编程思路。
（2）源程序。
习题69
69-1 组合数
69-2 求余数
69-3 SuperGCD