有四个超时了,求大佬优化下

P1045 [NOIP2003 普及组] 麦森数

stoneoceam @ 2022-06-13 14:02:05

#include<iostream>
#include<cmath>

int kk[500] = {0};

using namespace std;
int main() {
    int p;
    cin >> p;
    int a;//位数
    a = floor(log10(2) * p) + 1;//2的n次方的位数公式
    cout << a << endl;

    kk[499] = 1;

    int k = 499 - a;
    if (k < 0)
        k = 0;
    for (int i = 0; i < p; i++) {
        int temp = 0;
        for (int j = 499; j >= k; j--) {
            int sum = kk[j] * 2 + temp;
            temp = sum / 10;
            sum = sum % 10;
            kk[j] = sum;
        }
    }
    kk[499] = kk[499] - 1;

    for (int i = 1; i <= 500; i++) {
        cout << kk[i-1];
        if(i%50==0) {
            cout << endl;
        }

    }

    return 0;
}

by DAI33DAI @ 2022-06-14 16:39:17

2^P 的后 500 位时,你暴力求解时间复杂度是 O(500P) 的,需要使用快速幂,将其降低到 O(500^2\log{P})


|