题解

154 条题解

  • 6
    @ 2016-12-28 12:30:59

    重点:用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;
    }

  • 1
    @ 2019-01-01 18:55:03

    感谢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])
    
    
  • 1
    @ 2017-08-14 21:56:09

    #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求位数

  • 0
    @ 2018-04-20 11:03:11

    感谢@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;
    }
    
  • 0
    @ 2017-05-24 16:22:26

    //最快麦森数,每个点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;
    }

  • 0
    @ 2017-03-12 08:52:58
    #include<cstdio>
    #define re register int
    #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
    //---------------------------True Code----------------------------
    #include<cmath>
    #include<cstring>
    const int base=1e4,length=125;
    struct big{
        int a[500];
        inline void clear(){memset(a,0,sizeof(a));}
        big operator*(big b){   
            big c;c.clear();c.a[0]=a[0]+b.a[0];
            for(re i=1;i<=a[0];i++)  
                for(re j=1;j<=b.a[0];j++){
                    c.a[i+j-1]+=a[i]*b.a[j];
                    c.a[i+j]+=c.a[i+j-1]/base;
                    c.a[i+j-1]%=base;
                }
            while(c.a[0]>length||c.a[c.a[0]]==0)c.a[c.a[0]--]=0;
            return c;
        }
        inline void out(){
            a[1]-=1;//麦森数是2^p -1 
            for(re i=125,sum=0;i;i--){
                printf("%d%d",a[i]/1000,a[i]/100%10);sum+=2;
                if(sum==50){puts(""),sum=0;}
                printf("%d%d",a[i]/10%10,a[i]%10);sum+=2;
                if(sum==50){puts(""),sum=0;}
            }
            puts("");
        }
    }ans,a;
    inline void powMod(int k){
        ans.clear();ans.a[0]=ans.a[1]=1;
        a.clear();a.a[0]=1;a.a[1]=2;
        for(;k;k>>=1,a=a*a)
            if(k&1)ans=ans*a;
        ans.out();
    }
    int main(){
        File("mason");
        int n;scanf("%d",&n);
        printf("%d\n",int(floor(log10(2)*n)+1));
        powMod(n);//麦森数就是一个快速幂 mod=10^500 
    return 0;
    }
    
  • 0
    @ 2016-12-21 22:17:16

    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欢呼

  • 0
    @ 2016-10-26 13:47:46

    #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;
    }

  • 0
    @ 2016-10-26 13:30:24

    JAO

  • 0
    @ 2016-10-10 13:56:40
    #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求位数

  • 0
    @ 2016-08-29 19:36:48
    #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;
    }
    
  • 0
    @ 2016-08-23 21:02:20

    快速幂+高精度
    求位数用换底公式或者用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
    @ 2016-03-02 23:29:14

    编译成功

    测试数据 #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;
    }

  • 0
    @ 2015-09-05 21:54:11

    ###原来要用快速幂啊

    记录信息
    评测状态 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);
    }

  • 0
    @ 2015-08-19 18:04:02

    该题为高精度快速幂,直接求即可,并且只求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

  • 0
    @ 2015-03-30 19:05:04

    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.

  • 0
    @ 2014-10-26 16:34:31

    #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);
    }
    }

  • 0
    @ 2014-10-25 23:14:39

    //其实就是高精度版快速幂。千万注意是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;
    }

  • 0
    @ 2014-10-13 00:05:19

    类似打表
    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
    @ 2014-08-24 14:25:51

    测试数据 #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;
    }

信息

ID
1223
难度
5
分类
数论 | 数位统计 点击显示
标签
递交数
3984
已通过
1408
通过率
35%
被复制
8
上传者