麦森数(转)
1 //形如2n-1的素數稱為麥森數，這時n一定也是個素數。但反過來不一定，即如果n是個素數。2n-1不一定也是素數。
2
3 #include<iostream>
4 #include<cmath>
5 #include<cstdio>
6 #include<cstring>
7 #define N 126
8 using namespace std;
9 int ans[N],anspow[N];
10 void mult(int ans[],int anspow[])
11 {
12 int i,j;
13 int c[N];
14 memset(c,0,sizeof(c));
15 for(i=0;i<N;i++)
16 {
17 for(j=0;j<N;j++)
18 {
19 if(i+j<N)//超出500位的部分不計算
20 {
21 c[i+j]+=ans[j]*anspow[i];
22 }
23 }
24 for(j=0;j<N-1;j++)
25 {
26 if(c[j]>=10000)
27 {
28 c[j+1]+=c[j]/10000;//壓4位
29 c[j]%=10000;
30 }
31 }
32 }
33 memcpy(ans,c,N*sizeof(int)); //復制函數
34 }
35 int main()
36 {
37 int P,i,j;
38 while(cin>>P)
39 {
40 memset(ans,0,sizeof(ans));
41 memset(anspow,0,sizeof(anspow));
42 printf("%d\n",(int)(P*log10(2)+1));
43 ans[0]=1;
44 anspow[0]=2;
45 /************關鍵部分計算2^P*******
46 2^p=（2^1）*（2^2）*（2^3）*（2^4）*（2^5）………………
47 簡單說下：P=5 -----101（二進制）
48 p & 1 =1（最右邊一位） -->>>ans=2 anspow=2
49 p>>1=110 anspow=2^2
50 p & 1 =0 此時表明2^3不存在 ans=2 anspow=2^4
51 p>>1=1
52 p & 1 =1 ------>>>>> ans=2^5
53 p>>1=0 ------結束
54 ************************************/
55 while(P)
56 {
57 if( P & 1)
58 mult(ans,anspow);
59 P>>=1;
60 mult(anspow,anspow);
61 }
62 ans[0]--;//2^P的個位為2，4，6，8，故可以-1
63 /****************輸出格式的控制************************/
64 for(i=124;i>=0;i--)
65 {
66 if(i%25==12)
67 {
68 printf("%02d\n%02d",ans[i]/100,ans[i]%100);
69 }
70 else
71 {
72 printf("%04d",ans[i]);
73 if(i%25==0) printf("\n");
74 }
75 }
76 /***************************************************/
77 }
78 return 0;
79 }
?
1 /*************麥森數****************/ 2 #include<iostream> 3 #include<cstdio> 4 #include<cmath> 5 #define N 100 //壓5位 6 using namespace std; 7 int ans[N]; 8 void mult(int t) 9 { 10 int i,temp,last=0; 11 for ( i=N-1; i>=0; i--) 12 { 13 temp=(ans[i]<<t)+last; //乘2^t，加進位 14 last=temp/100000; 15 ans[i]=temp-last*100000; //temp%100000 16 } 17 } 18 void output() 19 { 20 int i; 21 for(i=1;i<=N;i++) 22 { printf("%05d",ans[i-1]); 23 if (i%10==0)cout<<endl; 24 } 25 } 26 int main() 27 { 28 int P,times; 29 while(cin>>P) 30 { 31 memset(ans,0,sizeof(ans)); 32 ans[N-1]=1; 33 cout<<(int)(P*log10(2)+1)<<endl; 34 /***********************關鍵部分***************** 35 2^P=2^(14*times)*2^(P%14) 用移位 36 之所以取14的原因 2^14*(99999)=1.638382*10^9 在（int） 37 范圍，15以后都會超int，主要體現在mult()中 38 **********************************************/ 39 times=P/14; //只能到14 15以后壓縮時會超范圍 40 while(times--) 41 mult(14); 42 mult(P%14); 43 --ans[99]; 44 output(); 45 } 46 return 0; 47 }?
轉載于:https://www.cnblogs.com/hduacm/archive/2012/08/22/2650796.html
總結
- 上一篇： php社保个税计算器 V20180925
- 下一篇： 什么是纸娃娃系统