/ Vijos / 题库 / 麦森数 /

题解

154 条题解

  • 0
    @ 2014-08-16 19:35:27

    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-07-29 10:01:08

    #include<iostream>
    #include<cmath>
    using namespace std;
    const unsigned int MAX = 1000;
    const long long WIDTHMAX = 100000;
    const unsigned int WIDTH = 5;
    typedef struct node
    {
    long long val[MAX];
    unsigned int size;
    } BigInt;
    void PrintBigInt(BigInt a);
    BigInt MulBigInt(const BigInt & a, const BigInt & b);
    void PowBigInt(BigInt & c, unsigned int n);
    int main()
    {
    unsigned int p;
    cin >> p;
    cout << int(log10(2)*p) + 1 << endl;
    BigInt a;
    PowBigInt(a, p);
    a.val[0] -= 1;
    PrintBigInt(a);
    system("pause");
    return 0;
    }

    void PowBigInt(BigInt & c, unsigned int n)
    {
    int stack[MAX] = {0};
    int top = 0;
    while (n > 0)
    {
    stack[top++] = n % 2;
    n /= 2;
    }
    BigInt b;
    b.size = 1;
    b.val[0] = 2;
    c.size = 1;
    c.val[0] = 1;
    for (int i=top-1; i>=0; i--)
    {
    c = MulBigInt(c, c);

    if (stack[i] == 1)

    c = MulBigInt(b, c);
    }
    }
    void PrintBigInt(BigInt a)
    {
    while (a.size*WIDTH < 500)
    {
    a.val[a.size++] = 0;
    }
    while (a.size*WIDTH > 500)
    {

    a.size--;
    }
    for (int i=a.size-1; i>=0; i--)
    {
    if (a.val[i] < 10)
    cout << "0000";
    else if (a.val[i] < 100)
    cout << "000";
    else if (a.val[i] < 1000)
    cout << "00";
    else if (a.val[i] < 10000)
    cout << "0";

    cout << a.val[i];
    if (i % 10 == 0)
    cout << endl;
    }
    }
    BigInt MulBigInt(const BigInt & a, const BigInt & b)
    {
    if (a.size == 1 && a.val[0] == 0)
    return a;
    if (b.size == 1 && b.val[0] == 0)
    return b;
    const int LEN = 500 / WIDTH + 1;
    BigInt c;
    for (int i=0; i<MAX; i++)
    c.val[i] = 0;
    for (int i=0, j=0; i<b.size && i<LEN; i++)
    {
    for (j=0; j<a.size && j<LEN; j++)
    {
    c.val[i+j] += a.val[j] * b.val[i];
    c.val[i+j+1] += c.val[i+j] / WIDTHMAX;
    c.val[i+j] %= WIDTHMAX;
    }
    c.size = i + j;

    if (c.val[c.size] != 0)
    c.size++;

    }
    return c;

    }

  • 0
    @ 2014-07-05 21:46:46

    ###Block code
    /*happywu
    * 2014.7.5
    * vojos 1223
    */
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<cmath>
    using namespace std;
    typedef long long ll;
    int a[600],b[600],c[1200],ans[600];
    ll p;
    void mul(int *a,int *b)
    {
    memset(c,0,sizeof(c));
    for(int i=1;i<=500;i++)
    for(int j=1;j<=500;j++)
    {
    c[i+j-1]+=a[i]*b[j]%10;
    c[i+j]+=a[i]*b[j]/10;
    }
    for(int i=1;i<=500;i++)
    {
    c[i+1]+=c[i]/10;
    c[i]=c[i]%10;
    }
    for(int i=1;i<=500;i++)
    a[i]=c[i];
    }
    void quick_power()
    {
    ans[1]=1;
    a[1]=2;
    while(p)
    {
    if(p&1)mul(ans,a);
    mul(a,a);
    p>>=1;
    }
    }
    void subtract()
    {
    if(ans[1]>=1)
    {
    ans[1]--;
    return;
    }
    int i=1;
    ans[i]--;
    while(ans[i]<0 && i<=501)
    {
    ans[i]=9;
    ans[i+1]--;
    i++;
    }
    }
    int main()
    {
    cin>>p;
    int wei=p*log10(2)+1;
    cout<<wei<<endl;
    quick_power();
    subtract();
    for(int i=500;i>=1;i--)
    {
    printf("%d",ans[i]);
    if((i-1)%50==0)printf("\n");
    }
    return 0;
    }

  • 0
    @ 2014-04-21 21:38:01

    刘明晓你在搞神马啊！！！

  • 0
    @ 2014-04-20 16:23:31

    #include <iostream>
    #include <math.h>
    #include <algorithm>
    #include <stdio.h>
    #include <string.h>
    using namespace std;
    int a[10000],ans[10000],c[10000];
    int p,n;

    void pingfang(int a[],int b[])
    {
    int i,j,k;
    k=0;
    memset(c,0,sizeof(c));
    for (i=0;i<500;i++)
    for (j=0; j<500-i+1;j++){
    c[i+j]+=a[i]*b[j];
    k= c[i+j] / 10;
    c[i+j+1]=c[i+j+1]+k;
    c[i+j] %= 10;
    }
    for (i=0;i<500;i++) a[i]=c[i];
    }
    int main()
    {
    cin>>p;
    cout<<int (p*log10(2)+1)<<endl;
    memset(ans,0,sizeof(ans));
    memset(a,0,sizeof(a));
    a[0]=2;
    ans[0]=1;
    while (p>0) {
    if (p % 2==1) pingfang(ans,a);

    p /=2;
    pingfang(a,a);
    }

    ans[0]--;
    for (int i=499;i>=0;i--){
    cout<<ans[i];
    if (i % 50==0) cout<<endl;
    }
    system("pause");
    return 0;
    }
    #include <iostream>
    #include <math.h>
    #include <algorithm>
    #include <stdio.h>
    #include <string.h>
    using namespace std;
    int a[10000],ans[10000],c[10000];
    int p,n;

    void pingfang(int a[],int b[])
    {
    int i,j,k;
    k=0;
    memset(c,0,sizeof(c));
    for (i=0;i<500;i++)
    for (j=0; j<500-i+1;j++){
    c[i+j]+=a[i]*b[j];
    k= c[i+j] / 10;
    c[i+j+1]=c[i+j+1]+k;
    c[i+j] %= 10;
    }
    for (i=0;i<500;i++) a[i]=c[i];
    }
    int main()
    {
    cin>>p;
    cout<<int (p*log10(2)+1)<<endl;
    memset(ans,0,sizeof(ans));
    memset(a,0,sizeof(a));
    a[0]=2;
    ans[0]=1;
    while (p>0) {
    if (p % 2==1) pingfang(ans,a);

    p /=2;
    pingfang(a,a);
    }

    ans[0]--;
    for (int i=499;i>=0;i--){
    cout<<ans[i];
    if (i % 50==0) cout<<endl;
    }
    system("pause");
    return 0;
    }
    #include <iostream>
    #include <math.h>
    #include <algorithm>
    #include <stdio.h>
    #include <string.h>
    using namespace std;
    int a[10000],ans[10000],c[10000];
    int p,n;

    void pingfang(int a[],int b[])
    {
    int i,j,k;
    k=0;
    memset(c,0,sizeof(c));
    for (i=0;i<500;i++)
    for (j=0; j<500-i+1;j++){
    c[i+j]+=a[i]*b[j];
    k= c[i+j] / 10;
    c[i+j+1]=c[i+j+1]+k;
    c[i+j] %= 10;
    }
    for (i=0;i<500;i++) a[i]=c[i];
    }
    int main()
    {
    cin>>p;
    cout<<int (p*log10(2)+1)<<endl;
    memset(ans,0,sizeof(ans));
    memset(a,0,sizeof(a));
    a[0]=2;
    ans[0]=1;
    while (p>0) {
    if (p % 2==1) pingfang(ans,a);

    p /=2;
    pingfang(a,a);
    }

    ans[0]--;
    for (int i=499;i>=0;i--){
    cout<<ans[i];
    if (i % 50==0) cout<<endl;

    }

    system("pause");
    return 0;
    }

  • 0
    @ 2013-11-17 17:24:58

    program mason;
    var n:array[1..500] of integer;
    i,j,k,s,m:longint;
    p,p0:longint;
    begin
    assign(input,'mason.in');
    reset(input);
    assign(output,'mason.out');
    rewrite(output);
    read(p);
    writeln(trunc((p*ln(2))/ln(10)+1));
    for i:=1 to 500 do n[i]:=0;
    n[1]:=1;
    m:=1;
    for i:=1 to 26 do m:=m*2;
    p0:=p mod 26;
    p:=p div 26;
    for i:=1 to p do
    begin
    k:=0;
    for j:=1 to 500 do
    begin
    s:=n[j]*m+k;
    k:=s div 10;
    n[j]:=s mod 10
    end;
    end;
    for i:=1 to p0 do
    begin
    k:=0;
    for j:=1 to 500 do
    begin
    s:=n[j]*2+k;
    k:=s div 10;
    n[j]:=s mod 10;
    end;
    end;
    n[1]:=n[1]-1;
    for i:=9 downto 0 do
    begin
    for j:=50 downto 1 do write(n[i*50+j]);
    writeln;
    end;
    close(input);
    close(output);
    end.

  • 0
    @ 2013-08-27 23:13:23

    明天写 快速幂+高精度
    爷明天来搞你！！

  • 0
    @ 2013-08-27 21:59:51

    从0分到10分，我无奈了

  • 0
    @ 2013-08-04 13:25:56

    我就留个念...肯定还有更好的写法.
    import java.text.DecimalFormat;
    import java.util.Scanner;
    import java.math.BigInteger;
    public class Main {
    static Scanner cin=new Scanner(System.in);
    static int n;
    static BigInteger res=BigInteger.valueOf(2);
    static BigInteger tmod=BigInteger.valueOf(10);
    public static void main(String args[])
    {
    n=cin.nextInt();
    tmod=tmod.pow(500);
    res=res.modPow(BigInteger.valueOf(n), tmod).subtract(BigInteger.ONE).add(tmod);
    System.out.println((int)(n*Math.log10(2)+1));
    DecimalFormat DemicalTest=new DecimalFormat("00000000000000000000000000000000000000000000000000,00000000000000000000000000000000000000000000000000");
    String sres=DemicalTest.format(res);
    sres=sres.replace(',','\n');
    System.out.println(sres.substring(2));

    }
    }

  • 0
    @ 2013-07-07 22:30:09

    把取整trunc 记成 round~

    type
    cc=array[0..520]of longint;
    var
    ans:Longint;
    i,j,k,x,m,l,n,p:longint;
    a,b,c:cc;
    procedure plus(var a:cc;b:cc);
    begin
    fillchar(c,sizeof(c),0);
    n:=a[0];
    m:=b[0];
    for i:=1 to n do
    begin
    x:=0;
    for j:=1 to m do
    begin
    if i+j-1>510 then break;
    c[i+j-1]:=c[i+j-1]+a[i]*b[j]+x;
    x:=c[i+j-1]div 10;
    c[i+j-1]:=c[i+j-1] mod 10;
    end;
    if x<>0 then c[i+j]:=x;
    end;
    n:=i+j-1;
    if n>510 then n:=510;
    if (c[n+1]<>0)and(n<510) then inc(n);
    a:=c;
    a[0]:=n;
    end;
    begin
    read(p);
    writeln(trunc(p*ln(2)/ln(10))+1);
    n:=1;
    m:=0;
    a[1]:=2;
    a[0]:=1;
    b[1]:=1;
    b[0]:=1;
    while p>0 do
    begin
    if p and 1=1 then
    plus(b,a);
    plus(a,a);
    p:=p shr 1;
    end;
    j:=0;
    dec(b[1]);
    for i:=500 downto 1 do
    begin
    inc(j);
    write(b[i]);
    if j mod 50=0 then writeln;
    end;
    end.

  • 0
    @ 2012-09-30 13:55:27

    一样的程序 一样的测评机 结果如下 第一次：

    VijosNT Mini 2.0.5.7 Special for Vijos

    编译通过...

    ├ 测试数据 01：答案正确... (793ms, 584KB)

    ├ 测试数据 02：答案正确... (0ms, 584KB)

    ├ 测试数据 03：答案正确... (0ms, 584KB)

    ├ 测试数据 04：答案正确... (0ms, 584KB)

    ├ 测试数据 05：答案正确... (0ms, 584KB)

    ├ 测试数据 06：答案正确... (0ms, 584KB)

    ├ 测试数据 07：答案正确... (0ms, 584KB)

    ├ 测试数据 08：答案正确... (0ms, 584KB)

    ├ 测试数据 09：答案正确... (0ms, 584KB)

    ├ 测试数据 10：运行超时... (?, 512KB)

    ---|---|---|---|---|---|---|---|-

    Unaccepted / 90 / ? / 584KB

    第二次：

    VijosNT Mini 2.0.5.7 Special for Vijos

    编译通过...

    ├ 测试数据 01：答案正确... (0ms, 584KB)

    ├ 测试数据 02：答案正确... (0ms, 584KB)

    ├ 测试数据 03：答案正确... (0ms, 584KB)

    ├ 测试数据 04：答案正确... (0ms, 584KB)

    ├ 测试数据 05：答案正确... (0ms, 584KB)

    ├ 测试数据 06：答案正确... (0ms, 584KB)

    ├ 测试数据 07：答案正确... (0ms, 584KB)

    ├ 测试数据 08：答案正确... (0ms, 584KB)

    ├ 测试数据 09：答案正确... (0ms, 584KB)

    ├ 测试数据 10：答案正确... (0ms, 584KB)

    ---|---|---|---|---|---|---|---|-

    Accepted / 100 / 0ms / 584KB

    vijos又抽了吗？？？？

  • 0
    @ 2012-08-08 17:33:57

    program ngfjbfjbg;

    type arr=array[1..500]of longint;

    var n,p,i,j:longint;

    ans,num:arr;

    function mul(a,b:arr):arr;

    var i,j:longint;

    c:arr;

    begin

    for i:=1 to 500 do c[i]:=0;

    for i:=1 to 500 do

    for j:=1 to 500-i+1 do

    c:=c+a[i]*b[j];

    for i:=1 to 499 do begin

    c:=c+c[i] div 10;

    c[i]:=c[i] mod 10;

    end;

    c[500]:=c[500] mod 10;

    mul:=c;

    end;

    begin

    read(p);

    n:=p;

    ans[1]:=1; num[1]:=2;

    while p>0 do begin

    if p mod 2=1 then ans:=mul(ans,num);

    p:=p div 2;

    num:=mul(num,num);

    end;

    writeln(trunc(n*ln(2)/ln(10))+1);

    dec(ans[1]); p:=1;

    for i:=500 downto 1 do

    begin

    if p=50 then begin writeln(ans[i]);p:=1;end

    else begin write(ans[i]); inc(p); end;

    end;

    end.

  • 0
    @ 2010-04-08 21:58:25

    问题一：求位数。由求指数公式我们可知2^p-1的位数为log(10)/log(2)*p+1，但是由于pascal语言中没有log函数，所以我们可以将其写成p*ln(2)/ln(10)+1。

    问题二：2^p的运算。我们可以采用二分法来解决这个问题，如果已知2^(p/2)我们只需将它在自乘以便就可以得到2^p。这样就省去了一半的运算量。由此我们可到函数mul(p,ans)

    Function mul(p)

    if p=1

    then mul ->2

    else

    T ->mul(p div 2)

    mul ->t*t

    if p mod 2=1 then mul ->mul*2

    这样算法的时间复杂度就为log(n)*高精度乘法的时间。

    但是如果本题用递归来写的话，因为高精度数字所占内存太大，这样很有可能在建栈的时候内存溢出，所以我们要把递归写成递推，观察每次迭代的p的变化，我们将其写成如下形式：

    t ->2

    n ->1

    while p0

    if p为奇数 then n ->n*t

    t ->t*t

    p ->p div 2

    至于高精度乘法是一个基础问题，这里不再累述。

    源程序详见我的博客上的日志http://zhurui250.blog.163.com/blog/static/137270520201001693543791/

  • 0
    @ 2009-11-09 22:55:22

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：0ms

    我SB啊

    算500位就可以了我全算出来

    结果TLE

  • 0
    @ 2009-11-08 15:33:24

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分：100 有效耗时：0ms

    AC！

    二分快速幂+高精~~~~

    晒晒程序

    Var

    a,b:array [0..1001] of Longint;

    n,i,j:Longint;

    Procedure quick(k:Longint);

    Var

    i,c,j,l:Longint;

    Begin

    If k=0 Then Exit;

    quick(k div 2);

    If k mod 20 Then c:=2 Else c:=1;

    For l:=1 to 500 Do

    For i:=1 to 500 Do Inc(b,a[i]*a[l]*c);

    For i:=1 to 500 Do Begin

    b:=b+b[i] div 10;

    b[i]:=b[i] mod 10;

    End;

    a:=b;

    Fillchar(b,sizeof(b),0);

    End;

    Begin

    Readln(n);

    Writeln(trunc(ln(2)/ln(10)*n)+1);

    a[1]:=1;

    quick(n);

    Dec(a[1]);

    For i:=500 downto 2 Do Begin

    Write(a[i]);

    If i mod 50=1 Then Writeln;

    End;

    Writeln(a[1]);

    Readln;

    End.

  • 0
    @ 2009-11-08 09:09:16

    快速幂的循环次数一直搞错了 最后才写成递归

    const maxn=1000000;

    type arr=array[0..maxn] of integer;

    var c,now,ss:arr;

    p,num,i,j:longint;

    procedure init;

    begin

    readln(p);

    ss[0]:=1;

    ss[1]:=2;

    end;

    procedure add(var ans,a,b:arr);

    var i,j,k:longint;

    max:integer;

    begin

    fillchar(ans,sizeof(ans),0);

    for i:=1 to a[0] do

    for j:=1 to b[0] do

    inc(ans,a[i]*b[j]);

    max:=a[0]+b[0];

    for i:=1 to max-1 do

    begin

    inc(ans,ans[i] div 10);

    ans[i]:=ans[i] mod 10;

    end;

    k:=max;;

    while (ans[k]=0)and(k>1)do

    dec(k);

    if k>500

    then k:=500;

    ans[0]:=k;

    end;

    procedure swap;

    var i:longint;

    begin

    for i:=0 to now[0] do

    c[i]:=now[i];

    end;

    procedure work(num:longint);

    var i,j:longint;

    begin

    if num

  • 0
    @ 2009-11-07 09:00:05

    分治，一定要分治!!!

  • 0
    @ 2009-11-07 00:36:40

    var n,l,p,len,i:longint;

    a,b:array[1..2000]of longint;

    procedure doit(p:longint);

    var i1,i2,i3:longint;

    begin

    if p=0 then exit;

    doit(p div 2);

    if odd(p) then p:=2 else p:=1;

    fillchar(b,sizeof(b),0);

    for i1:=1 to 500 do

    for i2:=1 to 500 do

    begin

    b[i1+i2-1]:=b[i1+i2-1]+a[i2]*a[i1]*p;

    if b[i1+i2-1]>=10 then

    begin

    b[i1+i2]:=b[i1+i2]+b[i1+i2-1] div 10;

    b[i1+i2-1]:=b[i1+i2-1] mod 10;

    end;

    end;

    a:=b;

    end;

    begin

    read(n);

    l:=trunc(ln(2)/ln(10)*n)+1;

    a[1]:=1;

    doit(n);

    writeln(l);

    a[1]:=a[1]-1;

    for i:=500 downto 1 do

    begin

    write(a[i]);

    if (i-1) mod 50=0 then writeln;

    end;

    end.

  • 0
    @ 2009-11-03 14:03:45

    编译通过...

    ├ 测试数据 01：答案正确... 0ms

    ├ 测试数据 02：答案正确... 0ms

    ├ 测试数据 03：答案正确... 0ms

    ├ 测试数据 04：答案正确... 0ms

    ├ 测试数据 05：答案正确... 0ms

    ├ 测试数据 06：答案正确... 0ms

    ├ 测试数据 07：答案正确... 0ms

    ├ 测试数据 08：答案正确... 0ms

    ├ 测试数据 09：答案正确... 0ms

    ├ 测试数据 10：答案正确... 0ms

    ---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|--

    Accepted 有效得分：100 有效耗时：0ms

    program ex;

    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:=sta+out[i]*out[j]

    else

    sta:=sta+out[i]*out[j]*2;

    for i:=1 to 500 do

    begin

    out[i]:=sta[i] mod 10;

    sta:=sta+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 20=1 then writeln;

    end;

    writeln(out[1]-1);

    end.

  • 0
    @ 2009-10-31 08:48:55

    分治才是王道！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

麦森数

信息

ID
1223
难度
5
分类
数论 | 数位统计 点击显示
标签
递交数
4067
已通过
1445
通过率
36%
被复制
19
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1