C语言程序设计100例之（69）：麦森数

本文主要是介绍C语言程序设计100例之（69）：麦森数，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

例69 麦森数

问题描述

形如2^p-1的素数称为麦森数，这时P一定也是个素数。但反过来不一定，即如果P是个素数。2^p-1不一定也是素数。到1998年底，人们已找到了37个麦森数。最大的一个是P=3021377，它有909526位。麦森数有许多重要应用，它与完全数密切相关。

任务：从文件中输入P (1000<P<3100000)，计算2^p-1的位数和最后500位数字（用十进制高精度数表示）

输入

文件中只包含一个整数P(1000<P<3100000)

输出

第1行：十进制高精度数2^p-1的位数。

第2-11行：十进制高精度数2^p-1的最后500位数字。（每行输出50位，共输出10行，不足500位时高位补0）

不必验证2^p-1与P是否为素数。

输入样例

1279

输出样例

386

00000000000000000000000000000000000000000000000000

00000000000000104079321946643990819252403273640855

38615262247266704805319112350403608059673360298012

23944173232418484242161395428100779138356624832346

49081399066056773207629241295093892203457731833496

61583550472959420547689811211693677147548478866962

50138443826029173234888531116082853841658502825560

46662248318909188018470682222031405210266984354887

32958028878050869736186900714720710555703168729087

（1）编程思路。

由于2^p的个位数字只可能是2、4、6、8，所以2^p-1 和2^p的位数相同。利用表达式(int)(p*log10(2))+1)可以轻松求得2^p-1 的位数。

2^p 的计算采用快速幂运算来完成。关于快速幂运算请参考前文“C语言程序设计100例之（41）：快速幂运算”（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。

（2）源程序。

#include <stdio.h>

#include <math.h>

#include <string.h>

#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<LEN;i++)

{

carry=0;

for (j=0;j<LEN-i;j++)

{

tmp=c[i+j]+a[j]*b[i]+carry;

c[i+j]=tmp%10000;

carry=tmp/10000;

}

for (i=0;i<LEN;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;

}

习题69

69-1 组合数

问题描述

给定正整数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 <stdio.h>

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<b)

{

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;

}

69-2 求余数

问题描述

给定一个基数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

输出样例

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 <stdio.h>

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;

}

69-3 SuperGCD

问题描述

Sheng bill 有着惊人的心算能力，甚至能用大脑计算出两个巨大的数的最大公约数！因此他经常和别人比赛计算最大公约数。有一天Sheng bill很嚣张地找到了你，并要求和你比赛，但是输给 Sheng bill 岂不是很丢脸！所以你决定写一个程序来教训他。

输入

共两行，第一行一个整数a，第二行一个整数 b（0<a,b≤10¹⁰⁰⁰⁰）。

输出

一行，表示a和b的最大公约数。

输入样例

输出样例

（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 <stdio.h>

#include <string.h>

#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<len;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<len;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)<strlen(b)) return 0;

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<len1;i++) // 将b的末尾添加0到与a等长

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 <stdio.h>

#include <string.h>

#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)<strlen(b)) return 0;

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]<y[0]) return 0;

else

{

int i;

for (i=1; i<=x[0]; i++)

if (x[i]>y[i]) return 1;

else if (x[i]<y[i]) return 0;

}

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。

这篇关于C语言程序设计100例之（69）：麦森数的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

C/C++教程