算法训练麦森数

转自https://www.cnblogs.com/Liberty-163/p/8157619.html

算法训练麦森数

时间限制：1.0s 内存限制：256.0MB

锦囊1

二分，高精度计算。

锦囊2

使用数组来保存答案的最后500位，实现乘法运算。计算幂时使用二分，则计算a^b先算a^(floor(b/2))，再平方一下，根据需要看是不是再乘a。

问题描述

　　形如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

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<cmath>
 6 using namespace std;
 7 
 8 int a[502] = {0}, b[502];
 9 
10 void cal()
11 {
12     int i, j, k;
13     memset(b, 0, sizeof(b));
14     for(i = 1; i <= 500; i++)
15     {
16         for(j = 1, k = i; j <= 500; j++)
17         {
18             b[k] = b[k] + a[i] * a[j];
19             k++;
20             if(i == 501)
21                 break;
22         }
23     }
24     for(i = 1; i <= 500; i++)
25     {
26         if(b[i] >= 10)
27         {
28             b[i + 1] += b[i] / 10;
29             b[i] = b[i] % 10;
30         }
31         a[i] = b[i];//更新快速幂
32     }
33 }
34 
35 void recur(int p)
36 {
37     if(p == 1 || p == 0)
38     {
39         a[1] = 2;
40         return;
41     }
42     else
43     {
44         recur(p / 2);
45         cal();
46         if(p % 2 == 1)
47         {
48             memset(b, 0, sizeof(b));
49             for(int i = 1; i <= 500; i++)
50             {
51                 b[i] += 2 * a[i];
52             }
53         }
54 
55         for(int i = 1; i <= 500; i++)
56         {
57             if(b[i] >= 10)
58             {
59                 b[i + 1] += b[i] / 10;
60                 b[i] = b[i] % 10;
61             }
62             a[i] = b[i];
63         }
64     }
65 }
66 
67 int main()
68 {
69     int p;
70     cin >> p;
71     cout << int(log10(2) * p +1);
72     recur(p);
73     a[1] -= 1;
74     for(int i = 500; i > 0; i--)
75     {
76         if(i % 50 == 0)
77         {
78             cout << endl;
79         }
80         cout << a[i];
81     }
82     return 0;
83 }

算法训练 麦森数

算法训练麦森数