洛谷 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;
}
上一篇:python基础-模块


下一篇:【wikioi】1922 骑士共存问题(网络流/二分图匹配)