看到这么大的数字就知道考高精度+快速幂+乘法。
高精度快速幂:
vector<int> power(int n) {//快速幂
vector<int> ans = {1};
vector<int> base = {2};
while(n) {
if(n & 1) ans = mul(ans,base);//如果是奇数就多乘一个
base = mul(base,base);
n >>= 1;
}
return ans;
}
高精度乘法优化:
vector<int> mul(vector<int>& a,vector<int>& b) {//高精度模板
vector<int> ans(500,0);
for(int i = 0; i < a.size(); i++) {
if(i >= 500) break;//控制计算位数,其他题可以去掉
for(int j = 0; j < b.size(); j++) {
if(i + j >= 500) break;//控制计算位数,其他题可以去掉
ans[i + j] += a[i] * b[j];
ans[i + j + 1] += ans[i + j] / 10;
ans[i + j] %= 10;
}
}
while(ans.size() > 1 && ans.back() == 0) ans.pop_back();//去除前导零
return ans;
}
完整代码:
#include <bits/stdc++.h>
using ull = unsigned long long;
using namespace std;
vector<int> mul(vector<int>& a,vector<int>& b) {//高精度模板
vector<int> ans(500,0);
for(int i = 0; i < a.size(); i++) {
if(i >= 500) break;//控制计算位数
for(int j = 0; j < b.size(); j++) {
if(i + j >= 500) break;//控制计算位数
ans[i + j] += a[i] * b[j];
ans[i + j + 1] += ans[i + j] / 10;
ans[i + j] %= 10;
}
}
while(ans.size() > 1 && ans.back() == 0) ans.pop_back();//去除前导零
return ans;
}
vector<int> power(int n) {//快速幂
vector<int> ans = {1};
vector<int> base = {2};
while(n) {
if(n & 1) ans = mul(ans,base);//如果是奇数就多乘一个
base = mul(base,base);
n >>= 1;
}
return ans;
}
int main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int p; cin >> p;
vector<int> ans = power(p);
//位数
cout << (int)(p * log10(2)) + 1 << endl;
//输出格式控制,写的很烂,能输出就行
int dig = max(0, (int)(500 - ans.size()));//计算要补充的0个数
int cnt = 0;//记录当前行输出了几个字符
for(int i = 0; i < dig; i++) {
if(cnt == 50) {//换行条件
cout << endl;
cnt = 0;
}
cout << 0;
cnt++;
}
for(int i = ans.size() - 1; i > 0; i--) {
if(cnt == 50) {//换行条件
cout << endl;
cnt = 0;
}
cout << ans[i];
cnt++;
}
cout << ans[0] - 1;//特殊处理最后一位
return 0;
}

京公网安备 11010502036488号