#题解#洛谷P1045 麦森数#快速幂#高精度乘法#

P1045 [NOIP 2003 普及组] 麦森数 - 洛谷

分析

1. 2^{p-1的位数，易知：跟2}p的位数相同，为[log10(2)*p]+1

2. 求末尾500位数字：高精度乘法+快速幂

代码

#include<bits/stdc++.h>
#define int  long long
#define endl '\n'
using namespace std;
const int N = 1500;int ans[N], a[N];
int l = 1;
int len = 1;
int c[N];
void pw(int b)
{ans[1] = 1;a[1] = 2;for (; b; b >>= 1){if (b & 1){memset(c, 0, sizeof c);for (int i = 1; i <= len; i++)for (int j = 1; j <= l; j++)c[i + j - 1] += ans[i] * a[j];len = min(len + l - 1,500ll);for (int i = 1; i <= len ; i++)c[i + 1] += c[i] / 10, c[i] %= 10;while (c[len + 1] and len < 500){len = min(500ll, len + 1);c[len + 1] += c[len] / 10;c[len] %= 10;}for (int i = 1; i <= len; i++)ans[i] = c[i];}memset(c, 0, sizeof c);for (int i = 1; i <= l; i++)for (int j = 1; j <= l; j++)c[i + j - 1] += a[j] * a[i];l = min(2 * l - 1,500ll);for (int i = 1; i <= l; i++)c[i + 1] += c[i] / 10, c[i] %= 10;while (c[l + 1] and l < 500){l = min(500ll, l + 1);c[l + 1] += c[l] / 10;c[l] %= 10;}for (int i = 1; i <= l; i++)a[i] = c[i];}
}
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int p;cin >> p;pw(p);int xx = p * log10(2) +1;cout << xx  << endl;for (int i = 500; i >= 1; i--){if (i == 1)cout << ans[i] - 1;elsecout << ans[i];if ((500 - i + 1) % 50 == 0)cout << endl;}return 0;
}

错误/Trick总结

1. N开太大memset导致TLE

2. 只需对500位以内进行高精度乘法