例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，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/428441.html
標籤：C