例69 麦森数
问题描述
形如2p-1的素数称为麦森数，这时P一定也是个素数。但反过来不一定，即如果P是个素数。2p-1不一定也是素数。到1998年底，人们已找到了37个麦森数。最大的一个是P=3021377，它有909526位。麦森数有许多重要应用，它与完全数密切相关。
任务：从文件中输入P (1000<P<3100000)，计算2p-1的位数和最后500位数字（用十进制高精度数表示）
输入
文件中只包含一个整数P(1000<P<3100000)
输出
第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
（1）编程思路。
由于2p的个位数字只可能是2、4、6、8，所以2p-1 和2p的位数相同。利用表达式(int)(p*log10(2))+1)可以轻松求得2p-1 的位数。
2p 的计算采用快速幂运算来完成。关于快速幂运算请参考前文“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≤1010000）。
输出
一行，表示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。