写了个高精类,样例过了但输入比较大就超时
查看原帖
写了个高精类,样例过了但输入比较大就超时
555584
weiming3楼主2023/3/8 13:13

前面是一个高精度类,经检验没有大问题,本题样例也过了,我感觉问题在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;
}
2023/3/8 13:13
加载中...