重点：用log求位数
log a(b)的结果k表示a的k次方等于b
换底公式：log a(c)/log b(c)=log b(c)
log 10（k）向上取整表示k的位数
log 的运算满足规律loga（b*c）=loga（b）+loga（c）
所以，log a（b^c）=loga（b）*c
所以，log 10（2）*n可以表示2^n的位数
然后快速幂（省略不讲，可以自行bing一下）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int p,a[100002],b[520];
void fz(int n)
{
int i,j;
if(n==0) return;
fz(n/2);
for(i=1;i<=500;i++)
for(j=1;j<=500;j++)
if(n%2==0) a[i+j-1]=a[i+j-1]+b[i]*b[j];
else a[i+j-1]=a[i+j-1]+b[i]*b[j]*2;
for(i=1;i<=500;i++)
{
b[i]=a[i]%10;
a[i+1]=a[i+1]+a[i]/10;
}
memset(a,0,sizeof(a));
}
int main()
{
int i;
scanf("%d",&p);
b[1]=1;
fz(p);
cout<<int((log(2)/log(10))*p+1)<<endl;
for(i=500;i>1;i--)
{
cout<<b[i];
if(i%50==1) cout<<endl;
}
cout<<b[1]-1<<endl;
return 0;
}


感谢frankchenfu的提示。
Python解法

import math
x = int(input())


def fastmod(a, b, c):  #a^bmod(c)
    v = 1
    a = a % c
    while b != 0:
        if b & 1 == 1:
            v = (v * a) % c
        b >>= 1
        a = (a * a) % c
    return v


a = math.ceil(math.log(2, 10) * x)

print(a)

y = str(fastmod(2, x, 10**500) - 1)

if len(y) < 500:
    y = '0' * (500 - len(y)) + y

for i in range(10):
    print(y[50 * i:50 * i + 50])

感谢@frankchenfu 的log求位数思路

重点：用log求位数
log a(b)的结果k表示a的k次方等于b
换底公式：log a(c)/log b(c)=log b(c)
log 10（k）向上取整表示k的位数
log 的运算满足规律loga（b*c）=loga（b）+loga（c）
所以，log a（b^c）=loga（b）*c
所以，log 10（2）*n可以表示2^n的位数

关于快速幂:
维基百科
百度百科
实际上百度百科所介绍的只是维基百科中的基本方法,不过已经够用了

#include <iostream>
#include <vector>
#include <stack>
#include <cmath>
using namespace std;

struct BigInt{
    vector<int> vec;
    int len;

    BigInt(){}
    BigInt(int n){
        len = 0;
        while (n>0){
            vec.push_back(n % 10);
            n /= 10;
            len++;
        }
    }

    void show()
    {
        stack<int> s;
        for (int i = 0; i < 500 && i < this->len; ++i) {
            s.push(this->vec[i]);
        }
        while(s.size() < 500){
            s.push(0);
        }
        for (int i = 0; i < 10; ++i) {
            for (int j = 0; j < 50; ++j) {
                cout << s.top();
                s.pop();
            }
            cout << endl;
        }
    }

    BigInt operator *(BigInt b){
        BigInt c;
        for (int i = 0; i < b.len + this->len; ++i) {
            c.vec.push_back(0);
        }
        c.len = this->len + b.len;
        for (int i = 0; i < this->len; ++i) {
            for (int j = 0; j < b.len; ++j) {
                c.vec[i+j] += this->vec[i] * b.vec[j];
                c.vec[i+j+1] += c.vec[i+j] / 10;
                c.vec[i+j] %= 10;
            }
        }
        int k = c.vec.size()-1;
        while (c.vec[k] == 0){
            k--;
        }
        c.len = k+1;
        if(c.len <= 500)        //如果结果不到五百位，就直接返回
            return c;
        else{                   //否则返回后500位
            BigInt r;
            for (int i = 0; i < 500; ++i) {
                r.vec.push_back(c.vec[i]);
            }
            r.len = 500;
            return r;
        }
    }
};

BigInt pow(int a,int n){            //快速幂
    BigInt r(1);
    BigInt base(a);
    while (n > 0){
        if(n & 1){
            r = r * base;
        }
        base = base * base;
        n >>= 1;
    }
    return r;
}

int main()
{
    int p;
    cin >> p;
    int ans = (int)ceil(log10(2)*p);
    cout << ans << endl;
    BigInt a = pow(2,p);
    a.vec[0]--;         //2^n末尾不为零,-1后位数不变
    a.show();

    return 0;
}

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
long long p,ans[5001],len,f[5001],n;
void suan(int x)
{
if(x==0) return;
suan(x/2);
len=500;
while(f[len]==0&&len>1) len--;
for(int i=1;i<=len;i++)
{
for(int j=1;j<=len;j++)
{
if(i+j-1<=500)
{
if(x%2==0) ans[i+j-1]+=f[i]*f[j];
else ans[i+j-1]+=f[i]*f[j]*2;
}
}
}
n=0;
for(int i=1;i<=500;i++)
{
f[i]=ans[i]+n;
n=f[i]/10;
f[i]%=10;
}
f[500]%=10;
memset(ans,0,sizeof(ans));
}
int main()
{
cin>>p;
f[1]=1;
cout<<int(p*log10(2)+1)<<endl;
suan(p);
for(int i=500;i>1;i--)
{
cout<<f[i];
if(i%50==1) cout<<endl;
}
cout<<f[1]-1<<endl;
return 0;
}
Copy
p*log10(2)+1求位数

//最快麦森数，每个点3ms；
//不信自己发

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
//a,b相乘结果保存至a中，代码短；
void chen( long long x[],long long y[])
{
int i=1,h=0,len2=1;
long long c[101]={0};
while(x[i]==0)//优化
i++;
while(y[len2]==0)//优化
len2++;
for(int j=100;j>=i;j--)
{
for(int k=100;k>=len2;k--)
{
c[j-h]+=x[j]*y[k];
h++;
if(j-h<=0)break;
}
h=0;
}//模拟乘
for(int j=100;j>=1;j--)
{
c[j-1]+=c[j]/100000;
c[j]%=100000;
}//进位
for(int j=1;j<=100;j++)
x[j]=c[j];
}
int coun(long long x)
{
int len=0;
while(x!=0)
{
x/=10;
len++;
}
return len;
}//求一个数的len；
int main()
{
long long p,ans[101]={0},a[101]={0};
cin>>p;
a[100]=2;
ans[100]=1;
cout<<int(p*log10(2)+1)<<endl;//求2^n的位数
while(p!=0)
{
if(p%2==1)chen(ans,a);
chen(a,a);
p/=2;
}//优化快速幂
ans[100]-=1;//小细节
int g=1;
while(ans[g]==0)
{
cout<<"00000";
g++;
if((g-1)%10==0)cout<<endl;
}//格式控制
int len=0;
for(int i=g;i<=100;i++)
{
len=5-coun(ans[i]);
while(len!=0)
{
cout<<0;
len--;
}
cout<<ans[i];
if(i%10==0)cout<<endl;
}//格式控制
return 0;
}

var n,i,j:longint;
out:array[1..500] of longint;
sta:array[1..1000] of longint;
procedure solve(n:longint);
begin
if n=0 then exit;
solve(n div 2);
for i:=1 to 500 do
for j:=1 to 500 do
if n mod 2=0 then sta[i+j-1]:=sta[i+j-1]+out[i]*out[j]
else sta[i+j-1]:=sta[i+j-1]+out[i]*out[j]*2;
for i:=1 to 500 do
begin
out[i]:=sta[i] mod 10;
sta[i+1]:=sta[i+1]+sta[i] div 10;
end;
for i:=1 to 1000 do sta[i]:=0
end;
begin
assign(input,'mason.in');
assign(output,'mason.out');
reset(input);
rewrite(output);
readln(n);
writeln(trunc(ln(2)/ln(10)*n)+1);
out[1]:=1;
solve(n);
for i:=2 to 500 do
begin
write(out[502-i]);
if i mod 50=1 then writeln;
end;
writeln(out[1]-1);
close(input);
close(output);
end.
1223欢呼

#include <bits/stdc++.h>
using namespace std;
int a[100000],b[100000];
int main()
{
int i,j,k,l,m;
memset(a,0,sizeof(a));
long n;
cin>>n;
if(n==0) {
cout<<1<<endl<<1<<endl;
return 0;
}
a[0]=1;
m=0;
for(i=0;i<n;i++){
for(j=0;j<=i;j++){
a[j] *= 2;
a[j] += m;
m= a[j] / 10;
a[j] %= 10;
}

}
for(k=500;a[k]==0;k--);

cout<<k+1<<endl;
for(i=499;i>0;i--) {
cout<<a[i];
if(i%50==0) cout<<endl;
}
cout<<a[0]-1<<endl;
return 0;
}

JAO

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
long long p,ans[5001],len,f[5001],n;
void suan(int x)
{
    if(x==0) return;
    suan(x/2);
    len=500;
    while(f[len]==0&&len>1) len--;
    for(int i=1;i<=len;i++)
    {
        for(int j=1;j<=len;j++)
        {
            if(i+j-1<=500)
            {
                if(x%2==0) ans[i+j-1]+=f[i]*f[j]; 
                else ans[i+j-1]+=f[i]*f[j]*2;
            }
        }
    }
    n=0;
    for(int i=1;i<=500;i++)
    {
        f[i]=ans[i]+n;
        n=f[i]/10;
        f[i]%=10;
    }
    f[500]%=10;
    memset(ans,0,sizeof(ans));
}
int main()
{
    cin>>p;
    f[1]=1;
    cout<<int(p*log10(2)+1)<<endl;
    suan(p);
    for(int i=500;i>1;i--)
    {
        cout<<f[i];
        if(i%50==1) cout<<endl;
    }
    cout<<f[1]-1<<endl;
    return 0;
}

p*log10(2)+1求位数

#include<iostream>
#include<cmath>
using namespace std;
int n,i,j,out[501],sta[1001];

void solve(int n)
{
    if (n==0) return;
    solve(n/2);
    for (i=1;i<=500;i++)
      for (j=1;j<=500;j++)
      if (n%2==0) sta[i+j-1]+=out[i]*out[j];
      else sta[i+j-1]+=out[i]*out[j]*2;
      for (i=1;i<=500;i++)
      {
            out[i]=sta[i]%10;
            sta[i+1]+=sta[i]/10;
            }
    for (i=1;i<=1000;i++) sta[i]=0;
}
int main()
{
    cin>>n;
    cout<<floor(log(2)/log(10)*n+1)<<endl;
    out[1]=1;
    solve(n);
    for (i=500;i>=2;i--)
    {
        cout<<out[i];
        if (i%50==1) cout<<endl;
        }
    cout<<out[1]-1<<endl;
    return 0;
}

快速幂+高精度
求位数用换底公式或者用math库 因为2的倍数末尾不可能是0，所以减1位数不变
快速幂和高精度要一起写，传个数组就超时了
type arr=array[1..600]of longint;
var
p,i,j:longint;
a,d:arr;
function ksm(b,p:longint):arr;
var
k,i,j:longint;
a,c:arr;
begin
if p=1 then exit(d);
k:=p mod 2;
p:=p div 2;
a:=ksm(b,p);
fillchar(ksm,sizeof(ksm),0);
for i:=1 to 500 do
for j:=1 to 500 do
if i+j-1<=500 then
begin
inc(ksm[i+j],(ksm[i+j-1]+a[i]*a[j]) div 10);
ksm[i+j-1]:=(ksm[i+j-1]+a[i]*a[j]) mod 10;
end;
if k=1 then
begin
fillchar(c,sizeof(c),0);
for i:=1 to 500 do
begin
inc(c[i+1],(ksm[i]*2+c[i]) div 10);
c[i]:=(ksm[i]*2+c[i]) mod 10;
end;
ksm:=c;
end;
end;
begin
readln(p);
writeln(trunc(p*ln(2)/ln(10))+1);
fillchar(d,sizeof(d),0);
d[1]:=2;
a:=ksm(2,p);
dec(a[1]);
for i:=500 downto 1 do
begin
if (i<>500) and ((500-i) mod 50=0) then writeln;
write(a[i]);
end;
end.

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 484 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 484 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 480 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 484 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 480 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 484 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 484 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 484 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 480 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 484 KiB, score = 10
Accepted, time = 0 ms, mem = 484 KiB, score = 100

四位压一位+快速幂，同时只求最后500位
c++
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
int r[135]={0},base[135]={0},b2[135],c[290],n,i,tot=0;
char k[505];
void Pow(int b);
void multiply(int s1[],int s2[],int to[]);
void multiply(int s1[],int s2[],int to[]){
to[0]=s1[0]+s2[0];
int i,j,x;
for(i=1;i<=s1[0];i++){
x=0;
for(j=1;j<=s2[0];j++){
x=s1[i]*s2[j]+x+to[i+j-1];
to[i+j-1]=x%10000;
x/=10000;
}
to[i+s2[0]]=x;
}
for(;to[0]>1&&to[to[0]]==0;)to[0]--;
}void Pow(int b){
int w;while(b!=0){
if(b&1){
multiply(r,base,c);
w=c[0];if(w>=132)w=c[0]=132;
memmove(r,c,sizeof(int)*(w+1));
memset(c,0,sizeof(c));
}memmove(b2,base,sizeof(base));
multiply(b2,base,c);
w=c[0];if(w>=132)w=c[0]=132;
memmove(base,c,sizeof(int)*(w+1));
memset(c,0,sizeof(c));
b>>=1;
}
}int main(){
scanf("%d",&n);
printf("%d\n",(int)floor(n*log10(2))+1);
r[0]=base[0]=r[1]=1;base[1]=2;Pow(n);r[1]--;
for(i=1;i<=125;i++)
sprintf(k+(i-1)*4,"%04d",r[125-i+1]);
for(i=1;i<=10;i++){
tot=k[i*50];k[i*50]='\0';
printf("%s\n",k+(i-1)*50);k[i*50]=tot;
}
return 0;
}

###原来要用快速幂啊

记录信息
评测状态 Accepted
题目 P1223 麦森数
递交时间 2015-09-05 21:51:52
代码语言 C++
评测机 VijosEx
消耗时间 222 ms
消耗内存 524 KiB
评测时间 2015-09-05 21:51:54
评测结果
编译成功

测试数据 #0: Accepted, time = 15 ms, mem = 524 KiB, score = 10
测试数据 #1: Accepted, time = 39 ms, mem = 520 KiB, score = 10
测试数据 #2: Accepted, time = 31 ms, mem = 524 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 524 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 520 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 524 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 520 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 524 KiB, score = 10
测试数据 #8: Accepted, time = 31 ms, mem = 524 KiB, score = 10
测试数据 #9: Accepted, time = 31 ms, mem = 524 KiB, score = 10
Accepted, time = 222 ms, mem = 524 KiB, score = 100
代码
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int a[510]={1,1};
int num[510]={1,2};
int b[510];
int main()
{
int n;
scanf("%d",&n);

int ans=n*0.30102999566+1;
printf("%d\n",ans);

for(;n>0;)
{
if(n%2==1)
{
for(int i=1;i<=501;i++)
{int in=0;
for(int j=1;i+j<=501;j++)
{
b[i+j-1]+=a[i]*num[j]+in;
in=b[i+j-1]/10;
b[i+j-1]%=10;
}
}
memcpy(a,b,sizeof(b));
memset(b,0,sizeof(b));
}
n/=2;
for(int i=1;i<=501;i++)
{ int in=0;
for(int j=1;j+i<=501;j++)
{
b[i+j-1]+=num[i]*num[j]+in;
in=b[i+j-1]/10;
b[i+j-1]%=10;
}
}
memcpy(num,b,sizeof(b));
memset(b,0,sizeof(b));
}
for(int i=500;i>1;i--)
{
printf("%d",a[i]);
if((i-1)%50==0)printf("\n");
}
printf("%d",a[1]-1);
}

该题为高精度快速幂，直接求即可，并且只求500位

###代码如下

program p1223;
type ar=array[0..502] of longint;
var p,i,j:longint;
ans,two:ar;
function min(a,b:longint):longint;
begin
if a<b then exit(a);
exit(b);
end;

function mutiply(num1,num2:ar):ar;
var len1,len2:integer;
num3:ar;
begin
fillchar(num3,sizeof(num3),0);
num3[0]:=min(num1[0]+num2[0]-1,500);
len1:=num1[0];
len2:=num2[0];
for i:=1 to len1 do
for j:=1 to min(len2+i-1,500-i+1) do {乘法计算时 num3[i+j-1]:=num3[i+j-1]+(num1[i]*num2[j])只需500位 ，所以计算第二个乘数只需500位以内的 即min（len2+i-1,500-i+1）len2 +i-1<500-i+1 说明第二个乘数每位都有必要乘，∵乘完后位数在500位以内
∵ 500=（i+j-1）
∴ j=500-i+1 }
begin
num3[i+j-1]:=num3[i+j-1]+(num1[i]*num2[j]);
num3[i+j]:=num3[i+j]+num3[i+j-1] div 10;
num3[i+j-1]:=num3[i+j-1] mod 10;
end;
while num3[num3[0]+1]>0 do inc(num3[0]);
exit(num3);
end;

function calc(m:longint):ar;
begin
if m=1 then exit(two);
ans:=calc(m>>1);
if odd(m)
then exit(mutiply(mutiply(ans,ans),two))
else exit(mutiply(ans,ans));
end;

begin
assign(input,'D:/input/mason.txt');
reset(input);
assign(output,'D:/output/mason.txt');
rewrite(output);
readln(p);
writeln(trunc(p*ln(2)/ln(10))+1);
two[0]:=1;
two[1]:=2;
fillchar(ans,sizeof(ans),0);
ans:=calc(p);
dec(ans[1]);
for i:= 500 downto 1 do
begin
if ((500-i)+1) mod 50=0
then writeln(ans[i])
else write(ans[i]);
end;
close(input);
close(output);
end.

###评测结果

测试数据 #0: Accepted, time = 15 ms, mem = 860 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 864 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 848 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 832 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 828 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 824 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 816 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 820 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 860 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 868 KiB, score = 10
Accepted, time = 90 ms, mem = 868 KiB, score = 100

var
n:longint;
i,j:longint;
out:array[1..500] of longint;
sta:array[1..1000] of longint;
procedure solve(n:longint);
begin
if n=0 then
exit;
solve(n div 2);
for i:=1 to 500 do
for j:=1 to 500 do
if n mod 2=0
then
sta[i+j-1]:=sta[i+j-1]+out[i]*out[j]
else
sta[i+j-1]:=sta[i+j-1]+out[i]*out[j]*2;
for i:=1 to 500 do
begin
out[i]:=sta[i] mod 10;
sta[i+1]:=sta[i+1]+sta[i] div 10;
end;
for i:=1 to 1000 do sta[i]:=0
end;
begin
readln(n);
writeln(trunc(ln(2)/ln(10)*n)+1);
out[1]:=1;
solve(n);
for i:=500 downto 2 do
begin
write(out[i]);
if i mod 50=1 then writeln
end;
writeln(out[1]-1);
end.

#include<cmath>
#include<cstring>
#include<iostream>
using namespace std;
int r[500]={0},d[500]={0},t[500];
void m(int*a,int*b)
{
int i,k;
memset(t,0,sizeof(t));
for(i=0;i<500;i++)
for(k=0;k<500;k++)
if(i+k<500)
t[i+k]+=a[i]*b[k];
else
break;
for(i=0;i<499;i++)
{
t[i+1]+=t[i]/10;
a[i]=t[i]%10;
}
a[499]=t[499]%10;
}
main()
{
int i,n;
r[0]=1;
d[0]=2;
cin>>n;
cout<<int(n*log10(2)+1)<<endl;
while(n)
{
if(n&1)
m(r,d);
m(d,d);
n>>=1;
}
r[0]--;
cout<<char(r[499]+48);
for(i=499;i>0;i--)
{
if(!(i%50))
cout<<endl;
cout<<char(r[i-1]+48);
}
}

//其实就是高精度版快速幂。千万注意是50个数一行！坑我WA了一次。
#include <stdio.h>
#include <math.h>
#define LENGTH 500

int result[LENGTH];
int delta[LENGTH];
int temp[LENGTH];
//delta是快速幂时的增量；temp是times函数中临时存放结果的数组。所有高精度数的个位都放在[0]

void times(int *num1,int *num2){
//该函数把num1*num2的结果暂时存放在temp中，最后再把temp的结果复制到num1
//其实相当于num1*=num2的高精度实现
int i,k;
for(i=0;i<LENGTH;i++)
temp[i]=0;
for(i=0;i<LENGTH;i++){
for(k=0;k<LENGTH;k++){
//下面的判断用于防越界（因为根据题意，所有数组长度都是500，大于500位的不必计算）
if(i+k<LENGTH)
temp[i+k]+=num1[i]*num2[k];
else
break;
}
}
for(i=0;i<LENGTH-1;i++){
temp[i+1]+=temp[i]/10;
num1[i]=temp[i]%10;
}
num1[LENGTH-1]=temp[LENGTH-1]%10;
}
int main(){
int i,n;

//初始化
for(i=0;i<LENGTH;i++){
result[i]=0;
delta[i]=0;
}
result[0]=1;
delta[0]=2;

scanf("%d",&n);
printf("%d\n",(int)(n*log10(2))+1);
//输出结果位数（因为2^n的个位肯定不为0，故不存在位数变动）

while(n>0){
//快速幂
if(n&1)
times(result,delta);
times(delta,delta);
n>>=1;
}
//对个位减一
result[0]--;

//每50个一行输出
putchar('0'+result[LENGTH-1]);
for(i=LENGTH-1;i>0;i--){
if((i)%50==0)
putchar('\n');
putchar('0'+result[i-1]);
}
return 0;
}

类似打表
P1223麦森数
Accepted

记录信息

评测状态 Accepted
题目 P1223 麦森数
递交时间 2014-10-13 00:04:05
代码语言 C++
评测机 上海红茶馆
消耗时间 198 ms
消耗内存 576 KiB
评测时间 2014-10-13 00:04:07

评测结果

编译成功

foo.cpp: In function 'int main()':
foo.cpp:132:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
foo.cpp:145:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
foo.cpp:148:41: warning: unknown conversion type character 'l' in format [-Wformat]
foo.cpp:148:41: warning: too many arguments for format [-Wformat-extra-args]

测试数据 #0: Accepted, time = 31 ms, mem = 572 KiB, score = 10

测试数据 #1: Accepted, time = 15 ms, mem = 568 KiB, score = 10

测试数据 #2: Accepted, time = 15 ms, mem = 572 KiB, score = 10

测试数据 #3: Accepted, time = 15 ms, mem = 572 KiB, score = 10

测试数据 #4: Accepted, time = 15 ms, mem = 568 KiB, score = 10

测试数据 #5: Accepted, time = 15 ms, mem = 568 KiB, score = 10

测试数据 #6: Accepted, time = 0 ms, mem = 572 KiB, score = 10

测试数据 #7: Accepted, time = 15 ms, mem = 576 KiB, score = 10

测试数据 #8: Accepted, time = 46 ms, mem = 576 KiB, score = 10

测试数据 #9: Accepted, time = 31 ms, mem = 568 KiB, score = 10

Accepted, time = 198 ms, mem = 576 KiB, score = 100

代码

#include <stdio.h>
#include <iostream>
#include <cstdio>
#include <string.h>
#include <math.h>
#include <cstdlib>

using namespace std;

int p;
unsigned long long ans[500 + 2];
int i , j;
int jw;
int s;
unsigned long long sum[500 + 2];
unsigned long long smalltable[500 + 2] = { 6 , 7 , 3 , 9 , 2 , 0 , 9 , 4 , 1 , 1 , 5 , 8 , 4 , 8 , 1 , 2 , 6 , 7 , 3 , 5 , 4 , 5 , 6 , 9 , 7 , 1 , 8 , 0 , 7 , 7 , 2 , 4 , 8 , 2 , 2 , 8 , 0 , 0 , 8 , 8 , 2 , 5 , 5 , 3 , 4 , 5 , 7 , 1 , 5 , 2 , 6 , 2 , 8 , 8 , 3 , 8 , 7 , 5 , 7 , 2 , 5 , 1 , 9 , 8 , 0 , 5 , 4 , 5 , 0 , 2 , 3 , 4 , 9 , 1 , 4 , 6 , 8 , 7 , 8 , 4 , 3 , 8 , 2 , 5 , 5 , 1 , 0 , 6 , 2 , 7 , 3 , 8 , 5 , 5 , 2 , 4 , 0 , 8 , 3 , 5 , 5 , 7 , 2 , 8 , 5 , 0 , 3 , 6 , 6 , 1 , 2 , 7 , 5 , 9 , 1 , 8 , 0 , 0 , 6 , 1 , 9 , 3 , 0 , 2 , 7 , 6 , 9 , 8 , 5 , 3 , 8 , 7 , 7 , 5 , 9 , 4 , 5 , 5 , 0 , 2 , 9 , 1 , 9 , 0 , 2 , 0 , 9 , 3 , 3 , 4 , 9 , 8 , 8 , 0 , 4 , 5 , 1 , 5 , 2 , 3 , 8 , 1 , 3 , 5 , 8 , 9 , 5 , 1 , 2 , 4 , 0 , 4 , 0 , 4 , 8 , 5 , 8 , 9 , 7 , 7 , 1 , 2 , 0 , 7 , 2 , 1 , 8 , 1 , 4 , 6 , 9 , 3 , 5 , 9 , 9 , 8 , 9 , 5 , 6 , 0 , 2 , 7 , 1 , 3 , 3 , 8 , 8 , 7 , 6 , 2 , 1 , 6 , 7 , 1 , 9 , 2 , 1 , 8 , 2 , 6 , 3 , 2 , 2 , 3 , 1 , 8 , 0 , 0 , 2 , 2 , 5 , 0 , 3 , 8 , 5 , 2 , 6 , 6 , 0 , 7 , 6 , 1 , 7 , 2 , 0 , 0 , 9 , 2 , 4 , 0 , 0 , 5 , 6 , 7 , 7 , 4 , 3 , 9 , 0 , 0 , 9 , 8 , 5 , 0 , 4 , 1 , 9 , 7 , 0 , 8 , 4 , 8 , 4 , 9 , 7 , 3 , 2 , 0 , 6 , 5 , 0 , 5 , 8 , 5 , 4 , 4 , 8 , 9 , 8 , 0 , 9 , 8 , 6 , 1 , 4 , 4 , 3 , 1 , 8 , 6 , 2 , 3 , 3 , 0 , 7 , 9 , 1 , 2 , 2 , 4 , 6 , 1 , 6 , 3 , 5 , 9 , 4 , 6 , 1 , 1 , 3 , 3 , 2 , 6 , 5 , 0 , 6 , 9 , 2 , 6 , 4 , 4 , 9 , 8 , 0 , 8 , 8 , 9 , 3 , 2 , 6 , 1 , 8 , 5 , 5 , 6 , 9 , 9 , 4 , 0 , 9 , 0 , 7 , 9 , 3 , 5 , 3 , 6 , 6 , 4 , 0 , 4 , 0 , 6 , 2 , 0 , 7 , 1 , 3 , 7 , 4 , 9 , 3 , 6 , 3 , 8 , 8 , 3 , 6 , 4 , 6 , 3 , 6 , 4 , 5 , 1 , 6 , 1 , 8 , 7 , 4 , 4 , 2 , 6 , 8 , 4 , 3 , 6 , 0 , 0 , 9 , 9 , 6 , 2 , 9 , 8 , 2 , 4 , 1 , 7 , 8 , 4 , 4 , 0 , 0 , 4 , 2 , 8 , 4 , 1 , 9 , 7 , 7 , 8 , 8 , 6 , 0 , 0 , 0 , 0 , 8 , 2 , 2 , 1 , 3 , 5 , 4 , 1 , 9 , 8 , 9 , 9 , 2 , 1 , 9 , 3 , 5 , 8 , 1 , 3 , 5 , 6 , 6 , 6 , 1 , 6 , 5 , 3 , 1 , 3 , 9 , 5 , 2 , 4 , 1 , 3 , 3 , 5 , 5 , 0 , 3 , 6 , 8 , 0 , 6 , 9 , 8 , 1 , 1 , 7 , 4 , 4 , 3 , 7 , 7 , 2 , 6 , 4 , 7 , 8 , 9 , 8 , 3 , 6 , 4 , 6 , 9 , 5 , 4 , 4 };
unsigned long long bigtable[500 + 2] ={ 6 , 7 , 3 , 9 , 0 , 1 , 7 , 6 , 2 , 2 , 2 , 6 , 1 , 7 , 8 , 0 , 0 , 0 , 7 , 1 , 4 , 0 , 2 , 8 , 0 , 5 , 7 , 4 , 7 , 9 , 6 , 8 , 1 , 2 , 7 , 5 , 4 , 7 , 3 , 0 , 1 , 1 , 9 , 0 , 1 , 0 , 4 , 1 , 5 , 9 , 0 , 9 , 5 , 4 , 6 , 5 , 4 , 0 , 3 , 6 , 5 , 5 , 9 , 2 , 8 , 9 , 1 , 8 , 6 , 6 , 3 , 8 , 2 , 9 , 6 , 1 , 5 , 3 , 2 , 6 , 0 , 3 , 7 , 4 , 5 , 2 , 2 , 5 , 7 , 7 , 0 , 7 , 6 , 7 , 6 , 7 , 4 , 9 , 6 , 7 , 8 , 5 , 0 , 4 , 7 , 0 , 3 , 7 , 6 , 4 , 5 , 6 , 5 , 4 , 4 , 2 , 8 , 9 , 7 , 2 , 3 , 2 , 1 , 7 , 2 , 2 , 6 , 3 , 7 , 6 , 9 , 4 , 2 , 8 , 6 , 1 , 7 , 0 , 2 , 6 , 3 , 1 , 9 , 3 , 2 , 0 , 5 , 0 , 8 , 4 , 0 , 8 , 4 , 6 , 5 , 3 , 2 , 1 , 4 , 8 , 8 , 9 , 5 , 4 , 9 , 7 , 9 , 8 , 2 , 1 , 9 , 8 , 8 , 8 , 4 , 7 , 0 , 1 , 7 , 0 , 7 , 0 , 1 , 3 , 7 , 9 , 4 , 4 , 1 , 3 , 6 , 2 , 1 , 7 , 6 , 2 , 4 , 0 , 8 , 1 , 6 , 6 , 7 , 8 , 1 , 2 , 4 , 5 , 3 , 6 , 0 , 7 , 4 , 7 , 5 , 0 , 3 , 5 , 0 , 8 , 5 , 2 , 8 , 2 , 9 , 2 , 1 , 1 , 4 , 0 , 6 , 6 , 9 , 2 , 4 , 5 , 9 , 9 , 7 , 2 , 2 , 7 , 6 , 9 , 3 , 9 , 7 , 6 , 6 , 9 , 5 , 7 , 3 , 9 , 6 , 7 , 3 , 7 , 9 , 6 , 5 , 2 , 2 , 7 , 4 , 7 , 0 , 0 , 0 , 0 , 5 , 0 , 5 , 7 , 2 , 3 , 4 , 2 , 0 , 4 , 9 , 3 , 2 , 1 , 4 , 6 , 9 , 7 , 0 , 3 , 8 , 9 , 7 , 2 , 1 , 2 , 8 , 0 , 2 , 8 , 1 , 8 , 7 , 9 , 9 , 1 , 1 , 7 , 0 , 7 , 5 , 5 , 4 , 1 , 7 , 2 , 2 , 1 , 3 , 4 , 0 , 6 , 2 , 5 , 1 , 2 , 7 , 5 , 0 , 5 , 9 , 3 , 5 , 9 , 9 , 8 , 0 , 5 , 6 , 7 , 4 , 5 , 0 , 1 , 8 , 0 , 6 , 5 , 9 , 9 , 2 , 8 , 4 , 9 , 8 , 8 , 6 , 1 , 8 , 0 , 3 , 8 , 5 , 3 , 2 , 9 , 5 , 3 , 1 , 5 , 0 , 5 , 3 , 0 , 4 , 2 , 2 , 7 , 4 , 9 , 6 , 0 , 1 , 7 , 9 , 8 , 0 , 2 , 6 , 0 , 9 , 8 , 6 , 1 , 4 , 4 , 7 , 2 , 7 , 6 , 0 , 4 , 2 , 0 , 2 , 7 , 2 , 0 , 8 , 3 , 3 , 9 , 4 , 8 , 2 , 0 , 6 , 0 , 2 , 8 , 3 , 4 , 7 , 1 , 0 , 2 , 7 , 9 , 6 , 5 , 3 , 4 , 9 , 0 , 1 , 2 , 8 , 3 , 8 , 8 , 5 , 4 , 6 , 2 , 7 , 5 , 2 , 3 , 9 , 0 , 7 , 6 , 9 , 9 , 3 , 0 , 2 , 6 , 8 , 5 , 7 , 9 , 5 , 6 , 0 , 6 , 5 , 4 , 2 , 2 , 9 , 7 , 2 , 0 , 4 , 5 , 9 , 5 , 4 , 8 , 6 , 6 , 1 , 8 , 5 , 2 , 5 , 0 , 5 , 9 , 4 , 9 , 9 , 2 , 3 , 4 , 4 , 0 , 8 , 2 };
unsigned long long table[500 + 2] = { 6 , 7 , 3 , 9 , 0 , 1 , 3 , 8 , 8 , 9 , 8 , 3 , 4 , 3 , 7 , 4 , 0 , 3 , 5 , 5 , 1 , 5 , 2 , 0 , 7 , 9 , 5 , 2 , 0 , 4 , 8 , 0 , 2 , 3 , 2 , 2 , 6 , 9 , 3 , 8 , 6 , 5 , 1 , 1 , 8 , 3 , 3 , 6 , 9 , 7 , 7 , 9 , 6 , 7 , 2 , 2 , 4 , 7 , 3 , 5 , 0 , 9 , 3 , 7 , 5 , 3 , 0 , 7 , 5 , 4 , 9 , 3 , 1 , 9 , 7 , 9 , 6 , 2 , 3 , 6 , 6 , 7 , 7 , 4 , 1 , 8 , 0 , 9 , 7 , 9 , 2 , 1 , 6 , 6 , 9 , 2 , 8 , 4 , 0 , 1 , 3 , 1 , 8 , 3 , 5 , 1 , 7 , 2 , 7 , 0 , 5 , 4 , 7 , 3 , 3 , 5 , 2 , 1 , 2 , 5 , 1 , 7 , 4 , 8 , 1 , 8 , 4 , 3 , 7 , 0 , 1 , 1 , 2 , 8 , 0 , 0 , 4 , 7 , 7 , 4 , 3 , 5 , 1 , 3 , 9 , 5 , 2 , 4 , 3 , 3 , 0 , 4 , 5 , 1 , 1 , 0 , 9 , 8 , 9 , 5 , 4 , 7 , 6 , 9 , 4 , 4 , 8 , 9 , 8 , 1 , 3 , 6 , 4 , 7 , 7 , 3 , 1 , 0 , 1 , 8 , 8 , 8 , 1 , 3 , 1 , 1 , 9 , 9 , 5 , 6 , 8 , 3 , 3 , 3 , 6 , 8 , 7 , 0 , 1 , 7 , 4 , 4 , 6 , 2 , 8 , 4 , 5 , 4 , 4 , 5 , 4 , 6 , 0 , 4 , 7 , 5 , 1 , 0 , 5 , 8 , 7 , 9 , 2 , 7 , 8 , 1 , 8 , 1 , 9 , 0 , 9 , 0 , 8 , 0 , 6 , 9 , 6 , 2 , 5 , 8 , 9 , 6 , 6 , 0 , 8 , 4 , 7 , 0 , 1 , 9 , 0 , 7 , 9 , 5 , 4 , 8 , 1 , 5 , 3 , 2 , 1 , 9 , 3 , 8 , 0 , 7 , 2 , 2 , 7 , 3 , 1 , 1 , 2 , 9 , 5 , 0 , 1 , 1 , 0 , 0 , 4 , 0 , 8 , 5 , 7 , 3 , 3 , 9 , 4 , 6 , 2 , 8 , 7 , 2 , 1 , 9 , 7 , 8 , 5 , 5 , 7 , 6 , 8 , 3 , 9 , 3 , 1 , 3 , 8 , 1 , 6 , 1 , 3 , 7 , 2 , 7 , 6 , 1 , 5 , 9 , 6 , 1 , 5 , 4 , 2 , 8 , 2 , 5 , 6 , 6 , 0 , 3 , 1 , 6 , 9 , 9 , 6 , 4 , 2 , 3 , 0 , 0 , 0 , 2 , 7 , 9 , 6 , 5 , 5 , 5 , 3 , 6 , 3 , 6 , 1 , 7 , 7 , 3 , 7 , 2 , 6 , 3 , 5 , 6 , 0 , 0 , 5 , 8 , 2 , 6 , 5 , 3 , 9 , 4 , 2 , 0 , 4 , 1 , 8 , 7 , 1 , 4 , 2 , 9 , 9 , 7 , 1 , 6 , 0 , 7 , 0 , 9 , 1 , 5 , 9 , 9 , 2 , 0 , 7 , 3 , 8 , 2 , 5 , 7 , 3 , 3 , 7 , 6 , 8 , 7 , 9 , 2 , 3 , 1 , 4 , 1 , 9 , 1 , 9 , 1 , 6 , 4 , 1 , 4 , 9 , 1 , 7 , 9 , 2 , 1 , 2 , 8 , 8 , 7 , 8 , 1 , 6 , 6 , 1 , 3 , 5 , 4 , 7 , 6 , 8 , 4 , 6 , 0 , 0 , 9 , 6 , 8 , 6 , 4 , 4 , 4 , 4 , 6 , 6 , 9 , 2 , 3 , 9 , 5 , 9 , 8 , 9 , 8 , 2 , 9 , 9 , 5 , 7 , 3 , 3 , 3 , 7 , 5 , 9 , 2 , 0 , 3 , 4 , 1 , 2 , 6 , 4 , 3 , 5 , 4 , 0 , 1 , 8 , 4 , 6 , 2 , 1 , 9 , 5 , 6 };

void bigtime()
{
memset( sum , 0 , sizeof( sum ) );
jw = 0;
for( i = 0 ; i < 500 ; i++ )
for( j = 0 ; j < 500 - i ; j++ )
sum[i + j] += ans[i] * bigtable[j];
for( i = 0 ; i < 500 ; i++ )
{
sum[i] += jw;
jw = sum[i] / 10;
sum[i] %= 10;
}
for( i = 0 ; i < 500 ; i++ )
ans[i] = sum[i];
}

void time()
{
memset( sum , 0 , sizeof( sum ) );
jw = 0;
for( i = 0 ; i < 500 ; i++ )
for( j = 0 ; j < 500 - i ; j++ )
sum[i + j] += ans[i] * table[j];
for( i = 0 ; i < 500 ; i++ )
{
sum[i] += jw;
jw = sum[i] / 10;
sum[i] %= 10;
}
for( i = 0 ; i < 500 ; i++ )
ans[i] = sum[i];
}

void smalltime()
{
memset( sum , 0 , sizeof( sum ) );
jw = 0;
for( i = 0 ; i < 500 ; i++ )
for( j = 0 ; j < 500 - i ; j++ )
sum[i + j] += ans[i] * smalltable[j];
for( i = 0 ; i < 500 ; i++ )
{
sum[i] += jw;
jw = sum[i] / 10;
sum[i] %= 10;
}
for( i = 0 ; i < 500 ; i++ )
ans[i] = sum[i];
}

int main()
{
//freopen( "an.txt" , "w" , stdout );
while( scanf( "%d" , &p ) != EOF )
{
s = ( int )floor( p * log10( 2 ) ) + 1;
cout << s << endl;
memset( ans , -1 , sizeof( ans ) );
ans[0] = 1;
/*p = 100000;
for( i = 0 ; i < p ; i++ )
{
jw = 0;
for( j = 0 ; ans[j] != -1 && j < 500 ; j++ )
{
ans[j] = ans[j] * 2 + jw;
jw = ans[j] / 10;
ans[j] %= 10;
}
if( j != 500 )
if( jw )
ans[j] = jw;
}
for( i = 0 ; i < 500 ; i++ )
printf( "%d , " , ans[i] );*/
if( p >= 500000 )
{
for( i = 0 ; i < 500 ; i++ )
ans[i] = bigtable[i];
p -= 500000;
}
else if( p >= 100000 )
{
for( i = 0 ; i < 500 ; i++ )
ans[i] = table[i];
p -= 100000;
}
else if( p >= 2000 )
{
for( i = 0 ; i < 500 ; i++ )
ans[i] = smalltable[i];
p -= 2000;
}
while( p >= 500000 )
{
bigtime();
p -= 500000;
}
while( p >= 100000 )
{
time();
p -= 100000;
}
while( p > 2000 )
{
smalltime();
p -= 2000;
}
for( i = 0 ; i < p ; i++ )
{
jw = 0;
for( j = 0 ; ans[j] != -1 && j < 500 ; j++ )
{
ans[j] = ans[j] * 2 + jw;
jw = ans[j] / 10;
ans[j] %= 10;
}
if( j != 500 )
if( jw )
ans[j] = jw;
}
ans[0]--;
for( i = 500 - 1 ; i >= 0 ; i-- )
{
if( ans[i] == -1 )
printf( "0" );
else
printf( "%llu" , ans[i] );
if( i % 50 == 0 )
cout << endl;
}

cout << endl;
}
fclose( stdout );
return 0;
}

测试数据 #0: Accepted, time = 46 ms, mem = 272 KiB, score = 10

测试数据 #1: Accepted, time = 46 ms, mem = 272 KiB, score = 10

测试数据 #2: Accepted, time = 31 ms, mem = 272 KiB, score = 10

测试数据 #3: Accepted, time = 31 ms, mem = 272 KiB, score = 10

测试数据 #4: Accepted, time = 31 ms, mem = 276 KiB, score = 10

测试数据 #5: Accepted, time = 15 ms, mem = 272 KiB, score = 10

测试数据 #6: Accepted, time = 15 ms, mem = 276 KiB, score = 10

测试数据 #7: Accepted, time = 31 ms, mem = 276 KiB, score = 10

测试数据 #8: Accepted, time = 46 ms, mem = 276 KiB, score = 10

测试数据 #9: Accepted, time = 46 ms, mem = 276 KiB, score = 10

Accepted, time = 338 ms, mem = 276 KiB, score = 100

代码

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int N=510;
void mul(int* a, int* b)
{
int i,j,c[N];
memset(c,0,sizeof(c));
for(i=0;i<500;i++)
for(j=0;j<500;j++)
if(i+j<500)
{
c[i+j]+=a[i]*b[j];
c[i+j+1]+=c[i+j]/10;
c[i+j]=c[i+j]%10;
}
memcpy(a,c,500*sizeof(int));
}
int main()
{
int n,i,x;
int a[N],s[N];
memset(a,0,sizeof(a));
memset(s,0,sizeof(s));
cin>>n;
a[0]=2;
s[0]=1;
x=n;
while(x>0)
{
if(x%2==1)
mul(s,a);
x=x/2;
mul(a,a);
}
n=n*(log(2)/log(10))+1;
cout<<n<<endl;
s[0]--;
for(i=499;i>=0;i--)
{
if(i%50==49&&i!=499)
cout<<endl;
cout<<s[i];
}
return 0;
}

var
n:longint;
i,j:longint;
out:array[1..500] of longint;
sta:array[1..1000] of longint;

procedure solve(n:longint);
begin
if n=0 then
exit;
solve(n div 2);
for i:=1 to 500 do
for j:=1 to 500 do
if n mod 2=0 then sta[i+j-1]:=sta[i+j-1]+out[i]*out[j]
else sta[i+j-1]:=sta[i+j-1]+out[i]*out[j]*2;
for i:=1 to 500 do
begin
out[i]:=sta[i] mod 10;
sta[i+1]:=sta[i+1]+sta[i] div 10;
end;
for i:=1 to 1000 do
sta[i]:=0
end;
begin
readln(n);
writeln(trunc(ln(2)/ln(10)*n)+1);
out[1]:=1;
solve(n);
for i:=500 downto 2 do
begin
write(out[i]);
if i mod 50=1 then writeln
end;
writeln(out[1]-1);
end.