写了个高精类,样例过了但输入比较大就超时

P1045 [NOIP2003 普及组] 麦森数

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

你这有亿点点长


|