题解 | 麦森数-NOIP2003普及组复赛D题

实际上第二个比较容易实现，写个高精度外加快速幂就可以了。由于最后结果位数比较大，即使是效率很高的快速幂也会超时，所以我们要另想办法求2^N-1的位数。我们发现，2^N的一位不可能是0，2^N-1和2^N的位数实际上是一样的。而且，若某个数是10^K，那么这个数的位数是K+1。把2N写成(10^lg2)^N，求出就是最后答案的位数。

 #include <cstdio>
 #include <cstring>
 #include <cmath>
 
 const int maxn = 1e6 + 5;
 
  int p, ans[maxn], x[maxn], al, xl, c[maxn], cl;
  
  inline void mul(int a[], int b[], int& al, int bl) {
      memset(c, 0, sizeof(c));
      cl = 1;
     for (int i = 1; i <= al; ++i)
         for (int j = 1; j <= bl; ++j) {
              if (i + j - 1 > 500) break;
             c[i + j - 1] += a[i] * b[j];
              if (c[i + j - 1] > 9) {
                 c[i + j] += c[i + j - 1] / 10;
                  c[i + j - 1] %= 10;
             }
          }
     cl = al + bl;
      while (!c[cl] && cl > 0) --cl;
     for (int i = 1; i <= cl; ++i) a[i] = c[i];
      al = cl;
 }
 
  inline void quickpow() {
      ans[1] = 1, al = 1;
      x[1] = 2, xl = 1;
      while (p) {
          if (p & 1) mul(ans, x, al, xl);
         mul(x, x, xl, xl);
          p >>= 1;
     }
  }
  
  int main() {
     scanf("%d", &p);
      printf("%d\n", (int)(log10(2) * p + 1));
      quickpow();
      --ans[1];
      for (int i = 1; i < al; ++i)
          if (ans[i] < 0) --ans[i + 1], ans[i] += 10;
    for (int i = 10; i >= 1; --i) {
         if (i != 10) putchar('\n');
         for (int j = 50; j >= 1; --j)
              printf("%d", ans[(i - 1) * 50 + j] ? ans[(i - 1) * 50 + j] : 0);
     }
      return 0;
  }