这道题纯粹是考数学。编程复杂度不大（别看我写了一百多行其实有些是可以不必写的）。

计算位数不必用高精时刻存，不然可想而知时间复杂度之大。首先大家要知道一个数学公式 logn(a*b)=logn(a)+logn(b)至于证明翻数学书吧。而且，用log10(n)+1即可求出n的位数。

则2^p的位数=log10(2^p)+1=p*log10(2)+1。这样，我们算的时候就不必随时存着位数了。

但是，如果直接写高精和n次循环，时间复杂度依旧很高。所以我们就要用快速幂。幂的运算是初中内容，几个公式如下:n^a*n^b=n^(a+b)，(n^a)^b=n^(a*b)。

所以，我们就可以将乘方的复杂度优化成O(logn)了。

代码

#include <cmath>

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

const int MAXN = 2001;

char c[MAXN];

inline char *read()

{

    scanf("%s", c);

    return c;

}

struct Big_int

{

    int s[MAXN], idx;

    Big_int()

    {

        idx = 0;

        memset(s, 0, sizeof(s));

    }

    inline void operator = (char *c)

    {

        idx = strlen(c);

        for(int i = 0; i < idx; i++) s[i] = c[idx - i - 1] - '0';

    }

    inline void operator = (int x)

    {

    	idx = 0;

    	memset(s, 0, sizeof(s));

    	if(!x) idx++;

        while(x)

        {

            s[idx] = x % 10;

            x /= 10;

            idx++;

        }

    }

    inline void print()

    {

        if(!idx) printf("0");

        else for(int i = idx - 1; i >= 0; i--)

        {

        	if(!((i + 1) % 50)) puts("");

        	printf("%d", s[i]);

    	}

        puts("");

    }

};

inline Big_int operator + (const Big_int x, const Big_int y)

{

    Big_int ret;

    ret.idx = max(x.idx, y.idx) + 1;

    for(int i = 0; i < ret.idx; i++)

    {

        ret.s[i] += x.s[i] + y.s[i];

        if(ret.s[i] >= 10)

            ret.s[i + 1] += 1, ret.s[i] -= 10;

    }

    while(!ret.s[ret.idx - 1] && ret.idx > 1) ret.idx--;

    return ret;

}

inline bool operator < (const Big_int x, const Big_int y)

{

    if(x.idx < y.idx) return 1;

    if(x.idx > y.idx) return 0;

    for(int i = x.idx - 1; i >= 0; i--)

        if(x.s[i] ^ y.s[i])

            return x.s[i] < y.s[i];

    return 0;

}

inline Big_int operator - (Big_int x, Big_int y)

{

    Big_int ret;

    if(x < y) swap(x, y);

    ret.idx = x.idx;

    for(int i = 0; i < ret.idx; i++)

    {

        if(x.s[i] < y.s[i])

        {

            x.s[i] += 10;

            x.s[i + 1]--;

        }

        ret.s[i] = x.s[i] - y.s[i];

    }

    while(!ret.s[ret.idx - 1] && ret.idx > 1) ret.idx--;

    return ret;

}

inline Big_int operator * (const Big_int x, const Big_int y)

{

    Big_int ret;

    ret.idx = x.idx + y.idx;

    for(int i = 0; i < x.idx; i++)

        for(int j = 0; j < y.idx; j++)

        {

            ret.s[i + j] += x.s[i] * y.s[j];

            ret.s[i + j + 1] += ret.s[i + j] / 10;

            ret.s[i + j] %= 10;

        }

    while(!ret.s[ret.idx - 1] && ret.idx > 1) ret.idx--;

    return ret;

}

int p;

Big_int a, ans;

int main()

{

    int i, j, k, x, y;

	scanf("%d", &p);

	cout << floor(log(2) / log(10) * p + 1);

    ans = 1;

    a = 2;

	while(p)

    {

    	if(p & 1) ans = ans * a, ans.idx = min(ans.idx, 500);

    	a = a * a, a.idx = min(a.idx, 500);

    	p >>= 1;

    }

	a = 1;

    ans = ans - a;

    ans.idx = 500;

	ans.print();

    return 0;

}

巴特西

[luoguP1045] 麦森数（快速幂 + 高精度）

代码

最新文章

热门文章