这道题太精彩了！
我一开始想直接一波暴力算，然后叫上去只有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;
}