超了五秒多。。不知道为啥 是vector太慢了吗 那也不至于这么慢吧 加了注释求大佬解答
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include<vector>
using namespace std;
//高精度减法
vector<int> sub(vector<int>& a, vector<int>& b) {
vector<int> c;
for (int i = 0, t = 0; i < a.size(); i++) {
t = a[i] - t;
if (i < b.size())
t -=b[i];
c.push_back((t + 10) % 10);
if (t < 0)
t = 1;
else
t = 0;
}
while (c.size() > 1 && c.back() == 0)
c.pop_back();
return c;
}
//高精度乘法
vector<int> mul2(vector<int>& a, vector<int>& b) {
vector<int>c(100010);
for (int i = 0; i < a.size(); i++) {
for (int j = 0; j < b.size(); j++) {
c[i + j] += a[i] * b[j];
c[i + j + 1] += c[i + j] / 10;
c[i + j] %= 10;
}
}
while (c.size() > 1 && c.back() == 0)
c.pop_back();
return c;
}
//高精度快速幂
vector<int> highPow(int n) { //2^n
vector<int>ans = { 1 }; vector<int> t = { 2 };
while (n) {
if (n & 1) {
ans = mul2(ans, t); //ans*=t
}
t = mul2(t, t); //t*=t
n >>= 1;
}
return ans;
}
int main() {
int p; scanf("%d", &p);
vector<int>ans;
ans = highPow(p);
cout << ans.size() << endl;
vector<int> tmp={1};
vector<int>res;
res=sub(ans, tmp); //2^p-1
res.resize(500); //不够500位填充0
for (int i = 499; i >=0; i--) {
if (i != 499 && (i+1) % 50 == 0)
cout << "\n" << res[i];
else
cout << res[i];
}
return 0;
}