洛谷P1045麦森数（高精度乘法）

题目链接：https://www.luogu.org/problemnew/show/P1045

这题分两问：求位数，求后500位

求位数：公式log10(x)+1，把幂移到前面即可

求后500位：其实如果让求完整的数的话，那就麻烦了，数太多一定时间复杂度高；但现在是只求后500位啊！多的不用管只求这些就行啊，复杂度明显降下来了！求再多次幂，快速幂二分不断分+每次就500位这么小的复杂度，所以一定可以很快完成！

还有个大数乘法技巧就是：不用直接输入时，最好直接用int数组！（省去了char数组转换数字的时间且更方便）

额，又新学了个memcpy复制函数，和for循环一样效果

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <iomanip>
 5 #include <cstdio>
 6 #include <cstring>
 7 #include <cmath>
 8 using namespace std;
 9 typedef long long ll;
10 typedef unsigned long long ull;
11 const int maxn=500;
12 int r[maxn],a[maxn];
13 int c[maxn];
14 int p;
15 
16 void Mul_1()
17 {
18     for(int i=0;i<=maxn-1;i++)
19     {
20         for(int j=0;j<=maxn-1;j++)
21         {
22             if(i+j<=maxn-1)//只算后500位就行!其他不管!不能超越界限,否则报错!
23             {
24                 c[i+j]+=r[i]*a[j];
25                 while(c[i+j]>=10)
26                 {
27                     c[i+j]-=10;
28                     if(i+j+1<=maxn-1) c[i+j+1]+=1;//这里也不能超越界限,否则报错!
29                 }
30             }
31         }
32     }
33 
34     //for(int i=0;i<=maxn-1;i++) r[i]=c[i];
35     memcpy(r,c,sizeof(r));//新学函数hh
36     memset(c,0,sizeof(c));
37 }
38 
39 void Mul_2()//其实2和1一样,只是改了几小处
40 {
41     for(int i=0;i<=maxn-1;i++)
42     {
43         for(int j=0;j<=maxn-1;j++)
44         {
45             if(i+j<=maxn-1)
46             {
47                 c[i+j]+=a[i]*a[j];
48                 while(c[i+j]>=10)
49                 {
50                     c[i+j]-=10;
51                     if(i+j+1<=maxn-1) c[i+j+1]+=1;
52                 }
53             }
54         }
55     }
56 
57     //for(int i=0;i<=maxn-1;i++) a[i]=c[i];
58     memcpy(a,c,sizeof(a));
59     memset(c,0,sizeof(c));
60 }
61 
62 void Qpow(int b)
63 {
64     while(b)
65     {
66         if(b&1) Mul_1();
67         Mul_2();
68         b>>=1;
69     }
70 }
71 
72 int main()
73 {
74     ios::sync_with_stdio(false); cin.tie(0);
75 
76     cin>>p;
77 
78     r[0]=1;
79     a[0]=2;
80     Qpow(p);
81     r[0]-=1;//2的幂不可能0结尾,所以不用考虑借位情况大胆-1即可
82 
83     int answ=p*log10(2)+1;
84     cout<<answ<<endl;
85     for(int i=maxn-1;i>=0;i--)
86     {
87         cout<<r[i];
88         if(i%50==0) cout<<endl;
89     }
90     cout<<endl;
91 
92     return 0;
93 }

完。