P1045 [NOIP2003 普及组] 麦森数

大整数+快速幂

复杂度(O(500*500*log(p)))

其中，位数的计算方法：

由于(2^p)最低位不会是0，所以(2^p-1)和(2^p)有同样的位数，由于(10^x)的位数为(x + 1)，所以令(2^p=10^x)有(x = log_{10}^{2^p}=p*log_{10}^{2})，所以位数为(p*log_{10}^{2} + 1)

#include<iostream>
#include<cstring>
#include<cmath>

using namespace std;

const int N = 500;

int a[N];
int ans[N];
int backup[N];

int p;

void mul(int *a, int *b){
    memset(backup, 0, sizeof backup);
    
    for(int i = 0; i < N; i ++)
        for(int j = 0; j < N; j ++){
            if(i + j >= N) continue;
            backup[i + j] += a[i] * b[j];
        }
    
    
    int t = 0;
    for(int i = 0; i < N; i ++){
        backup[i] += t;
        t = backup[i] / 10;
        backup[i] %= 10;
    }
    
    memcpy(a, backup, sizeof backup);
}

void ksm(int e){
    a[0] = 2, ans[0] = 1;
    while(e){
       if(e & 1) mul(ans, a);
       mul(a, a);
       e >>= 1;
    }
}

int main(){
    cin >> p;
    ksm(p);
    ans[0] -= 1;
    
    if(ans[0] < 0){
        ans[0] += 10;
        for(int i = 1; i < 500; i ++)
            if(ans[i] == 0) ans[i] = 9;
            else{
                ans[i] --;
                break;
            }
    }
    
    cout << int(log10(2) * p + 1) << endl;
    
    for(int i = N - 1, k = 1; i >= 0; i --, k ++) cout << ans[i] << (k % 50 ? "" : "
");
    return 0;
}