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

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

0

输出样例

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 <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的最大公约数。

输入样例

12

54

输出样例

6

         （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）：麦森数的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！