洛谷 P1045 麦森数 （快速幂+高精度+算位数骚操作）

这道题太精彩了！

我一开始想直接一波暴力算，然后叫上去只有50分，50分超时

然后我改成万位制提高运算效率，还是只有50分

然后我丧心病狂开long long用10的10次方作为一位，也就是100亿进制

去做，然后交上去多过了一个点，60分

附上丧心病狂的代码

#include<cstdio>

#include<cctype>

#include<algorithm>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

#define _for(i, a, b) for(int i = (a); i <= (b); i++)

using namespace std;

typedef long long ll;

const int MAXN = 1123456 / 10;

const ll base = 1e10;

ll a[MAXN];

int len, n;

void cal()

{

    _for(i, 1, len) a[i] <<= 1;

    _for(i, 1, len)

    {

        a[i+1] += a[i] / base;

        a[i] %= base;

    }

    if(a[len+1])

    {

        len++;

        a[len+1] += a[len] / base;

        a[len] %= base;

    }

}

int main()

{

    scanf("%d", &n);

    len = 1; a[1] = 2;

    REP(i, 1, n) cal();

    int p = 1;

    a[p] -= 1;

    while(a[p] < 0)

    {

        a[p + 1]--;

        a[p] += base;

        p++;

    }

    if(a[len] == 0) len--;

    ll t = a[len], num = 0;

    while(t) t /= 10, num++;

    printf("%d\n", len * 10 - 10 + num);

    for(int i = 50, t = 0; i >= 1; i--, t++)

    {

        if(t == 5) puts(""), t = 0;

        printf("%010lld", a[i]);

    }

    return 0;

}

然后我最后还是看了题解

然后看到算位数真的是给折服的

还有这种操作？？？

由于10的x次方的位数是x+1

然后可以把2的p次方转化成类似10的x次方来算位数

然后这个时候就用到了log

一波骚操作可以得出位数就是p * lg(2) + 1

牛逼！

然后算前500位。

我竟然没看出这是个快速幂？？？？？？

用高精度做快速幂还是头一次。

不过稍微改一下就好了。

#include<cstdio>

#include<cctype>

#include<cstring>

#include<cmath>

#include<algorithm>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

#define _for(i, a, b) for(int i = (a); i <= (b); i++)

using namespace std;

typedef long long ll;

const int MAXN = 1123;

struct bignum

{

	ll s[MAXN]; int len;

	bignum() { memset(s, 0, sizeof(s)); len = 1; }

};

bignum operator * (const bignum& a, const bignum& b)

{

	bignum c;

	c.len = min(a.len + b.len - 1 , 500);

	_for(i, 1, a.len)

		_for(j, 1, b.len)

		{

			c.s[i+j-1] += a.s[i] * b.s[j];

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

			c.s[i+j-1] %= 10;

		}

	if(c.s[c.len+1] && c.len < 500) c.len++;

	return c;

}

int main()

{

	int b;

	scanf("%d", &b);

	printf("%d\n", (int)(b * log10(2)+ 1));

	bignum res; res.s[1] = 1;

	bignum a; a.s[1] = 2;

	while(b)

	{

		if(b & 1) res = res * a;

		b >>= 1;

		a = a * a;

	}

	res.s[1] -= 1;

	for(int i = 500; i >= 1; i--)

	{

		if(i != 500 && i % 50 == 0) puts(""); //这个写法很简便

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

	}

	puts("");

	return 0;

}

洛谷 P1045 麦森数 （快速幂+高精度+算位数骚操作）的相关教程结束。