P1045 麦森数 题解

题目描述 形如2^P-1的素数称为麦森数，这时P一定也是个素数。但反过来不一定，即如果P是个素数，2^P−1不一定也是素数。到1998年底，人们已找到了37个麦森数。最大的一个是P=3021377P=3021377，它有909526位。麦森数有许多重要应用，它与完全数密切相关。 任务：从文件中输入P（1000<P<3100000），计算2^P-1的位数和最后500位数字（用十进制高精度数表示）

题解 位数：由10^t 位数为t+1可知只要求出10的x次幂等于2，再用x代替2求出x^p 即可。已知log10(2)等于2，即x=log10(2)，可得出位数即为log10(2)*p+1。 输出：基础快速幂和高精度算法，没一次AC，基础算法需要再复习QAQ

AC代码

#include<bits/stdc++.h> using namespace std; const long long mod=10000000000; const int N=2001; int p,l=1,lb=1; int a[N]={},b[N]={},c[N]={}; int cf1(){ memset(c,0,sizeof(c)); for (int i = 1; i <= l; ++i){ for (int j = 1; j <= lb; ++j){ c[i+j-1] += a[i] * b[j]; c[i+j] += ( c[i+j-1] ) / 10; c[i+j-1] %= 10; } } int lc = l + lb; while( c[lc] == 0 ) -- lc; for(int i = 1;i <= lc; ++i){ a[i] = c[i]; } return lc>500?500:lc; } int cf2() { memset(c,0,sizeof(c)); for (int i = 1; i <= lb; ++i) { for (int j = 1; j <= lb; ++j) { c[i+j-1] += b[i] * b[j]; c[i+j] += ( c[i+j-1] ) / 10; c[i+j-1] %= 10; } } int lc = lb + lb; while( c[lc] == 0 ) -- lc; for(int i = 1;i <= lc; ++i){ b[i] = c[i]; } return lc>500?500:lc; } void qpow() { while( p ) { if( p & 1 ) l = cf1 ( ); p >>= 1; lb = cf2 (); } } int main() { scanf("%d",&p); printf("%d\n",int (log10(2)*p+1)); a[1] = 1; b[1] = 2; qpow(); --a[1]; for (int i = 500; i >= 1; --i) { printf("%d",a[i]); if ( ! ( (i-1) % 50 ) ) printf("\n"); } return 0; }