50分!help!

P1045 [NOIP2003 普及组] 麦森数

ZackofZHOU @ 2023-10-17 21:29:26

本蒟蒻写了快速幂 , 带高精乘 , TLE了5个点 , 测试信息

代码:

#include<algorithm>
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
int A[100010],B[100010],C[100010];
struct vli  
{
    vector <char> number;
    bool minis_zero = false;
    void Swap(vli b)
    {
        vector <char> n = b.number;
        b.number = number;
        number = n;
        bool x = b.minis_zero;
        b.minis_zero = minis_zero;
        minis_zero = x;
    }
    void get_string(string s)
    {
        if(s[0] == '-')
        {
            minis_zero = true;
            s.erase(s.begin() + 0);
        }
        number.clear();
        for(int i = 0;i < s.size();i++)
            number.push_back(s[i]);
    }
    void show()
    {
        for(int i = 0;i < number.size();i++)
            cout << number[i];
        cout << '\n';
    }
};
vli operator-(vli a,int b)
{
    vli ans;
    int lena = a.number.size();
    for(int i = lena - 1;i >= 0;i--)
        A[lena - i] = a.number[i] - '0';
    A[1] -= b;
    for(int i = 1;i <= lena;i++)
        if(A[i] < 0)
            A[i] += 10,A[i + 1]--;
    for(;A[lena] == 0;)
        lena--;
    for(int i = lena;i >= 1;i--)
        ans.number.push_back(A[i] + '0');
    for(int i = 0;i < 1010;i++)
        A[i] = 0,C[i] = 0;
    return ans;
}
vli operator*(vli a,vli b)
{
    vli ans;
    int lena = a.number.size(),lenb = b.number.size(),len = lena + lenb;
    for(int i = 0;i < lena;i++)
        A[lena - i] = a.number[i] - '0';
    for(int i = 0;i < lenb;i++)
        B[lenb - i] = b.number[i] - '0';
    for(int i = 1;i <= lena;i++)
        for(int j = 1;j <= lenb;j++)
            C[i + j - 1] += A[i] * B[j];
    for(int i = 1;i <= len;i++)
    {
        C[i + 1] += (C[i] / 10);
        C[i] %= 10;
    }
    for(;C[len] == 0;)
        len--;
    for(int i = len;i >= 1;i--)
        ans.number.push_back(C[i] + '0');
    for(int i = 0;i < 10010;i++)
        A[i] = B[i] = C[i] = 0;
    return ans;
}
int main()
{
    vli ans,two,s;
    int p,c = 0;
    ans.get_string("1");
    two.get_string("2");
    s = two;
    cin >> p;
    while(p > 0)
    {
        if(p & 1)
            ans = ans * s;
        s = s * s;
        p >>= 1;
    }
    ans = ans - 1;
    cout << ans.number.size() << '\n';
    if(ans.number.size() >= 500)
        for(int i = ans.number.size() - 500;i < ans.number.size();i++)
        {
            c++;
            cout << ans.number[i];
            if(c % 50 == 0)
                cout << '\n';
        }
    else
    {
        for(int i = 1;i <= 500 - ans.number.size();i++)
        {
            c++;
            cout << 0;
            if(c % 50 == 0)
                cout << '\n';
        }
        for(int i = 0;i < ans.number.size();i++)
        {
            c++;
            cout << ans.number[i];
            if(c % 50 == 0)
                cout << '\n';
        }
    }
    return 0;
}

请求各位dalao帮个忙QQL


by Turtle_Coffee @ 2023-10-17 21:46:31

qp(doge)


|