求助，高精度加不上

Dz8897 @ 2023-11-14 17:41:25

//这代码没有办法转成高精度啊
cpp
#include <bits/stdc++.h>
using namespace std;
long long JK[5500];
long long J(long long o){
    if(JK[o]==0){
        JK[o]=J(o-1)+J(o-2);
        return JK[o];   
    }else{
        return JK[o];   
    }
}
int main(){
    long long n;
    cin>>n;
    for(long long i=0;i<=3;i++) JK[i]=i;
    cout<<J(n);
}

by OldDriverTree @ 2023-11-14 17:56:32

@Dz8897 把 long long 类型改成高精度类型就行了啊

by IOI_AK_TLR @ 2023-11-14 18:04:34

@Dz8897

把你代码的 using namespace std; 后面加上下面这个高精度模板类，然后把你数组和函数里的 long long 改成 BigInteger 就行了

#define INF 0x3f3f3f3f

class BigInteger
{
public:
    using ll = long long;

    BigInteger() {};
    BigInteger(const string& s);
    BigInteger(ll a) :BigInteger(to_string(a)) {}
    BigInteger(const BigInteger& bInt) :nums(bInt.nums), isPositive(bInt.isPositive), length(bInt.length) {}
    BigInteger(BigInteger&& bInt) noexcept :nums(move(bInt.nums)), isPositive(bInt.isPositive), length(bInt.length) {}
    BigInteger(const vector<int>& vec, bool sign = true) :nums(vec), isPositive(sign) { cutLeadZero(); }

    friend istream& operator >>(istream& is, BigInteger& bInt)
    {
        string s;
        is >> s;
        bInt = move(BigInteger(s));
        return is;
    }
    friend ostream& operator <<(ostream& os, const BigInteger& bInt);
    operator string() const;
    const BigInteger& operator +() const { return *this; }
    BigInteger operator -() const
    {
        BigInteger tmp(*this);
        if (!tmp.isZero())
            tmp.isPositive = !isPositive;
        return tmp;
    }
    bool operator <(const BigInteger& bInt) const;
    bool operator <=(const BigInteger& bInt) const;
    bool operator ==(const BigInteger& bInt) const;
    BigInteger operator +(const BigInteger& bInt) const;
    BigInteger operator -(const BigInteger& bInt) const;
    BigInteger operator *(const BigInteger& bInt) const;
    pair<BigInteger, BigInteger> operator /(const BigInteger& bInt) const;
    int operator[](int idx) const { return nums[idx]; }
    BigInteger& operator =(const BigInteger& bInt)
    {
        if (bInt == *this)
            return *this;
        nums = bInt.nums;
        isPositive = bInt.isPositive;
        length = bInt.length;
        return *this;
    }
    BigInteger& operator =(BigInteger&& bInt)noexcept
    {
        nums = move(bInt.nums);
        isPositive = bInt.isPositive;
        length = bInt.length;
        return *this;
    }

    size_t size() const { return nums.size(); }
    void cutLeadZero();
    bool isZero() const;
    BigInteger absValue() const
    {
        return move(BigInteger(nums));
    }
    static BigInteger e(size_t n)
    {
        if (n <= 0)
            return move(BigInteger(vector<int>(1, 1)));
        int m = n / digit;
        n -= m * digit;
        vector<int> ans(m);
        string s = "1";
        s += move(string(n, '0'));
        ans.push_back(stoi(s));
        return move(BigInteger(ans));
    }

private:
    vector<int> nums;
    bool isPositive = 1;
    int length = 0;
    static int digit;
    static int mod;
};

int BigInteger::digit = 8;        
int BigInteger::mod = 100000000; 

BigInteger::BigInteger(const string& s)
{
    int n = s.size(), minIdx = 0;
    if(s[0]=='-')
        isPositive = false, minIdx = 1;
    else if(s[0]=='+')
        isPositive = true, minIdx = 1;
    for (int i = n - 1; i >= minIdx; i -= digit)
    {
        int beg = max(minIdx, i - digit + 1);
        nums.push_back(stoi(s.substr(beg, i - beg + 1)));
    }
    cutLeadZero();
}

ostream& operator <<(ostream& os, const BigInteger& bInt)
{
    os << (string)bInt;
    return os;
}

BigInteger::operator string() const
{
    string ans;
    if (!isPositive)
        ans += "-";
    int n = nums.size();
    for (int i = n - 1; i >= 0; i--)
    {
        string s = to_string(nums[i]);
        if (i != n - 1)
            ans += string(digit - s.size(), '0');
        ans += s;
    }
    return ans;
}

bool BigInteger::operator<(const BigInteger& bInt) const
{
    if (isPositive && !bInt.isPositive)
        return false;
    if (!isPositive && bInt.isPositive)
        return true;
    bool flag = true;
    if (!isPositive)
        flag = false; 
    if (length < bInt.length)
        return flag;
    else if (length > bInt.length)
        return !flag;
    int n = size();
    for (int i = n - 1; i >= 0; i--)
    {
        if (nums[i] < bInt[i])
            return flag;
        else if (nums[i] > bInt[i])
            return !flag;
    }
    return false;
}

bool BigInteger::operator<=(const BigInteger& bInt) const
{
    if (isPositive && !bInt.isPositive)
        return false;
    if (!isPositive && bInt.isPositive)
        return true;
    bool flag = true;
    if (!isPositive)
        flag = false; 
    if (length < bInt.length)
        return flag;
    else if (length > bInt.length)
        return !flag;
    int n = size();
    for (int i = n - 1; i >= 0; i--)
    {
        if (nums[i] < bInt[i])
            return flag;
        else if (nums[i] > bInt[i])
            return !flag;
    }
    return true;
}

bool BigInteger::operator==(const BigInteger& bInt) const
{
    if (length != bInt.length)
        return false;
    int n = size();
    for (int i = 0; i < n; i++)
        if (nums[i] != bInt[i])
            return false;
    return true;
}

BigInteger BigInteger::operator+(const BigInteger& bInt) const
{
    if (!bInt.isPositive)
        return *this - (-bInt); 
    if (!isPositive)
        return bInt - (-*this); 
    vector<int> ans;
    int n = size(), m = bInt.size(), sum = 0, i = 0, j = 0;
    while (i < n || j < m || sum)
    {
        if (i < n)
            sum += nums[i++];
        if (j < m)
            sum += bInt[j++];
        ans.push_back(sum % mod);
        sum /= mod;
    }
    return move(BigInteger(ans, isPositive));
}

BigInteger BigInteger::operator-(const BigInteger& bInt) const
{
    if (!bInt.isPositive)
        return *this + (-bInt); 
    if (!isPositive)
        return -((-*this) + bInt); 
    if (*this < bInt)
        return -(bInt - *this);
    vector<int> ans;
    int i = 0, j = 0, n = size(), m = bInt.size(), sum = 0;
    while (i < n || j < m || sum)
    {
        if (i < n)
            sum += nums[i++];
        if (j < m)
            sum -= bInt[j++];
        int flag = 0;
        if (sum < 0)
        {
            flag = -1;
            sum += mod;
        }
        ans.push_back(sum);
        sum = flag;
    }
    return move(BigInteger(ans));
}

BigInteger BigInteger::operator*(const BigInteger& bInt) const
{
    int n = size(), m = bInt.size();
    vector<int> ans(n + m);
    using ll = long long;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            ll tmp = ans[i + j] + nums[i] * 1ll * bInt[j];
            ans[i + j] = tmp % mod;
            ans[i + j + 1] += tmp / mod;
        }
    }
    return move(BigInteger(ans, isPositive == bInt.isPositive));
}

pair<BigInteger, BigInteger> BigInteger::operator/(const BigInteger& bInt) const
{
    BigInteger a = absValue();
    BigInteger b = bInt.absValue();
    if (b.isZero())
        return pair<BigInteger, BigInteger>(*this, move(b));
    if (a < b)
        return pair<BigInteger, BigInteger>(move(BigInteger(0)), *this);
    int len = a.length - b.length + 1;
    string ans;
    if (isPositive != bInt.isPositive)
        ans = "-";
    for (int i = 0; i < len; i++)
    {
        BigInteger tmp = e(len - i - 1) * b;
        int times = 0;
        while (tmp <= a)
        {
            a = a - tmp;
            ++times;
        }
        ans += times + '0';
    }
    a.isPositive = isPositive;
    return pair<BigInteger, BigInteger>(move(BigInteger(ans)), move(a));
}

void BigInteger::cutLeadZero()
{
    while (nums.size() > 1 && nums.back() == 0)
        nums.pop_back();
    if (nums.empty())
        length = 0;
    else
    {
        length = (nums.size() - 1) * digit + to_string(nums.back()).size();
    }
}

bool BigInteger::isZero() const
{
    return nums.size() == 1 && nums.back() == 0;
}