weiming3 @ 2023-03-08 13:13:43
前面是一个高精度类,经检验没有大问题,本题样例也过了,我感觉问题在main function里, 每一次的product*=2都会构造一次high_precision ,开销很大,有什么处理的好办法吗
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
class high_precision {
private:
string num1;
string num2;
public:
high_precision(string a, string b) {
num1 = a;
num2 = b;
}
string add() {
while (num1.size() < num2.size()) {
num1 = "0" + num1;
}
while (num2.size() < num1.size()) {
num2 = "0" + num2;
}
int carry = 0;
string res = "";
for (int i = num1.size() - 1; i >= 0; i--) {
int sum = num1[i] - '0' + num2[i] - '0' + carry;
carry = sum / 10;
res = to_string(sum % 10) + res;
}
if (carry) {
res = to_string(carry) + res;
}
return res;
}
string substract() {
while (num1.size() < num2.size()) {
num1 = "0" + num1;
}
while (num2.size() < num1.size()) {
num2 = "0" + num2;
}
int carry = 0;
string res = "";
for (int i = num1.size() - 1; i >= 0; i--) {
int differ = num1[i] - '0' - (num2[i] - '0') - carry;
if (differ < 0) {
differ += 10;
carry += 1;
} else {
carry = 0;
}
res = to_string(differ) + res;
}
while (res.size() > 0 && res[0] == '0') {
res.erase(0, 1);
}
return res;
}
string multiply() {
string res(num1.size() + num2.size(), '0');
int carry = 0;
for (int i = num1.size() - 1; i >= 0; i--) {
for (int j = num2.size() - 1; j >= 0; j--) {
int sum = (num1[i] - '0') * (num2[j] - '0') + ( res[i + j + 1] - '0') + carry;
res[i + j + 1] = sum % 10 + '0';
carry = sum / 10;
}
res[i] = (res[i] - '0' + carry) + '0';
carry = 0;
}
while (res.size() > 1 && res[0] == '0') {
res.erase(0, 1);
}
return res;
}
string divide() {
vector<int> dividend;
int divisor = 0;
for (int i = 0; i <= num2.size() - 1; i++) {
divisor += (int)pow(10, num2[num2.size() - 1 - i]) * (num2[i] - '0');
}
for (int i = 0; i <= num1.size() - 1; i++) {
dividend.push_back(num1[i] - '0');
}
int carry = 0;
vector<int> res;
for (int i = 0; i <= dividend.size() - 1; i++) {
int temp = carry * 10 + dividend[i];
carry = temp % divisor;
res.push_back(temp / divisor);
}
while (*res.begin() == 0 && res.size() > 0) {
res.erase(res.begin());
}
string ans;
for (int i = 0; i <= res.size() - 1; i++) {
ans[i] = res[i] + '0';
}
return ans;
}
};
int main() {
int p;
cin >> p;
string product = "1";
for (int i = 1; i <= p; i++) {
high_precision h("2", product);
product = h.multiply();
}
high_precision h(product, "1");
product = h.substract();
cout << product.size() << endl;
if (product.size() >= 500) {
for (int i = 0; i <= 49; i++) {
for (int j = 0; j <= 9; j++) {
cout << product[product.size() - 500 + i * 50 + j + 1];
}
cout << endl;
}
} else {
int k = 0;
for (int i = 1; i <= 500 - product.size(); i++) {
cout << "0";
k++;
if (k % 50 == 0) {
cout << endl;
}
}
for (int i = 0; i <= product.size() - 1; i++) {
if (k % 50 == 0) {
cout << endl;
}
cout << product[i];
k++;
}
}
return 0;
}
by allen2010 @ 2023-05-26 18:39:11
@weiming3 位数用数学公式计算。
by hjbaoyx @ 2023-07-25 10:02:22
你这有亿点点长