50分 超时求助
查看原帖
50分 超时求助
1021623
AVLw楼主2023/10/3 17:22

超了五秒多。。不知道为啥 是vector太慢了吗 那也不至于这么慢吧 加了注释求大佬解答

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include<vector>
using namespace std;
//高精度减法
vector<int> sub(vector<int>& a, vector<int>& b) {
    vector<int> c;
    for (int i = 0, t = 0; i < a.size(); i++) {
        t = a[i] - t;
        if (i < b.size())
            t -=b[i];
        c.push_back((t + 10) % 10);
        if (t < 0)
            t = 1;
        else
            t = 0;
    }
    while (c.size() > 1 && c.back() == 0)
        c.pop_back();
    return c;
}
//高精度乘法
vector<int> mul2(vector<int>& a, vector<int>& b) {
    vector<int>c(100010);
    for (int i = 0; i < a.size(); i++) {
        for (int j = 0; j < b.size(); j++) {
            c[i + j] += a[i] * b[j];
            c[i + j + 1] += c[i + j] / 10;
            c[i + j] %= 10;
        }
    }
    while (c.size() > 1 && c.back() == 0)
        c.pop_back();
    return c;
}
//高精度快速幂
vector<int> highPow(int n) {  //2^n  
    vector<int>ans = { 1 }; vector<int> t = { 2 };
    while (n) {
        if (n & 1) {
            ans = mul2(ans, t);  //ans*=t
        }
        t = mul2(t, t);   //t*=t
        n >>= 1;
    }
    return ans;
}
int main() {

    int p; scanf("%d", &p);
    vector<int>ans;
    ans = highPow(p);
    cout << ans.size() << endl;

    vector<int> tmp={1};
    vector<int>res;
    res=sub(ans, tmp);  //2^p-1
    res.resize(500);  //不够500位填充0
    for (int i = 499; i >=0; i--) {
        if (i != 499 && (i+1) % 50 == 0)
            cout << "\n" << res[i];
        else
            cout << res[i];
    }

    return 0;
}

2023/10/3 17:22
加载中...