看到这么大的数字就知道考高精度+快速幂+乘法。
高精度快速幂:
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; }