藍橋杯試題 算法訓練 麥森數 C/C++

試題 算法訓練 麥森數

資源限制

時間限制：1.0s 記憶體限制：256.0MB

問題描述

　　形如2P-1的素數稱為麥森數，這時P一定也是個素數。但反過來不一定，即如果P是個素數，2P-1不一定也是素數。到1998年底，人們已找到了37個麥森數。最大的一個是P=3021377，它有909526位。麥森數有許多重要應用，它與完全數密切相關。

　　任務：從檔案中輸入P（1000<P<3100000），計算2P-1的位數和最後500位數字（用十進制高精度數表示）

輸入格式

　　檔案中隻包含一個整數P（1000<P<3100000）

輸出格式

　　第一行：十進制高精度數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

思路：本題難點為數量大運算可能會逾時，這樣位數和最後的值就比較難求，是以求位數可以用一個以10為底2的對數再加一，(int)((log10(n!))+1)也就是這個式子，原本是求n的階乘的位數的，但是也可以求2的幂方的位數，變為：(int)((log10(2))*p+1)，p為幂次，底為2，這個公式由2 ^ p以10為底,變成 (int)((log10(2 ^ p))+1),p就得乘下來變成這個形式了(int)((log10(2))*p+1)，為什麼要加一呢，一個三位數對10運算下來，實際會變成兩位，是以得加一，而後500位的運算可以采用二分法和快速幂的做法來實作，在以前的文章中也寫過兩次了，是以這次直接上代碼吧。

代碼如下：

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
void han(int a[501],int b[501]){
	int c[501],i,j,k,t,s=0;
	memset(c,0,sizeof(c));
	for(i=499;i>=0;i--){
		k=i;s=0;
		for(j=499;j>=0;j--){
			t=a[i]*b[j];
			c[k]=c[k]+t%10+s;  //高精度乘法比如31乘31，需要1乘31加3乘31，而3乘31的位數會高一位，把平時乘法思想用代碼實作即可
			s=t/10+c[k]/10;
			c[k]=c[k]%10;	
			k--;
			if(k<0){
				break;
			}
		}
	}
	memcpy(a,c,sizeof(c));
}
int main(){
	int a[501],b[501],i,j,k,p;
	cin>>p;
	cout<<(int)((log10(2))*p+1)<<endl;
	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b));
	a[499]=2;b[499]=1;
	while(p>0){
		if(p%2==1){
			han(b,a);
		}
		han(a,a);
		p/=2;
	}
	for(i=0;i<500;i++){
		if(i%50==0 && i>0){
			cout<<endl;
		}
		if(i==499){
			cout<<b[i]-1;  //2的幂次最後一位不會為零，是以不用判斷
		} else{
			cout<<b[i];
		}
	}
}