怎么样使得这篇代码能够被优化到只需要500MB以下的内存?

灌水区

C_plus_plus_12345 @ 2024-11-29 20:17:22

#include<bits/stdc++.h>
using namespace std;

/*High-precision calculation define*/
int myCompare(string a, string b)
{
    if (a.size() != b.size())
    {
        if (a.size() > b.size())
            return 1;
        else
            return -1;
    }
    else
    {
        if (a > b)
            return 1;
        else if (a == b)
            return 0;
        else
            return -1;
    }
}
string myAdd(string a, string b)
{
    int n = max(a.size(), b.size()) + 1;
    vector<int>ans(n, 0);
    int i = a.size() - 1, j = b.size() - 1, k = n - 1;
    while (i >= 0 && j >= 0)
    {
        ans[k--] = (a[i--] - '0') + (b[j--] - '0');
    }
    while (j >= 0)
    {
        ans[k--] = (b[j--] - '0');
    }
    while (i >= 0)
    {
        ans[k--] = (a[i--] - '0');
    }
    string c = "";
    for (int i = n - 1; i > 0; i--)
    {
        if (ans[i] >= 10)
        {
            ans[i] -= 10;
            ans[i - 1]++;
        }
        c.insert(0, 1, ans[i] + '0');
    }

    if (ans[0] > 0)
    {
        c.insert(0, 1, ans[0] + '0');
    }
    return c;
}
string mySubtract(string a, string b)
{
    string c = "";
    if (myCompare(a, b) == 0)
        return "0";
    if (myCompare(a, b) == -1)
    {
        swap(a, b);
        c.push_back('-');
    }
    int n = a.size();
    vector<int>ans(n, 0);
    int i = a.size() - 1, j = b.size() - 1, k = n - 1;
    int t = 0;
    while (i >= 0)
    {
        char nowb;
        if (j >= 0) nowb = b[j];
        else nowb = '0';
        ans[k] = a[i] - nowb - t;
        if (ans[k] < 0)
        {
            t = 1;
            ans[k] += 10;
        }
        else t = 0;
        k--, i--, j--;
    }
    bool flag = true;
    for (int i = 0; i < n; i++)
    {
        if (flag && ans[i] == 0)
            continue;
        flag = false;
        c.push_back(ans[i] + '0');
    }
    return c;
}
string myMultiply(string a, string b)
{
    if (a == "0" || b == "0")
        return "0";
    vector<int>ans;
    int n = a.size(), m = b.size();
    ans.resize(n + m, 0);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            ans[i + j + 1] += (a[i] - '0') * (b[j] - '0');
        }
    }
    for (int i = n + m - 1; i > 0; i--)
    {
        if (ans[i] >= 10)
        {
            ans[i - 1] += (ans[i] / 10);
            ans[i] %= 10;
        }
    }
    string c = "";
    bool flag = true;
    for (int t = 0; t < n + m; t++)
    {
        if (flag && ans[t] == 0)
            continue;
        flag = false;
        c.push_back(ans[t] + '0');
    }
    return c;
}
vector<string>myDivide(string a, string b)
{
    vector<string>ans(2, "0");
    if (myCompare(a, b) == -1)
    {
        ans[1] = a;
        return ans;
    }
    else if (myCompare(a, b) == 0)
    {
        ans[0] = "1";
        return ans;
    }
    else
    {
        string res = "";
        int m1 = a.size(), m2 = b.size();
        string a1 = a.substr(0, m2 - 1);
        for (int i = m2 - 1; i < m1; i++)
        {
            if (a1 == "0")
                a1 = "";
            a1.push_back(a[i]);
            int e = 0;
            while (myCompare(a1, b) >= 0)
            {
                e++;
                a1 = mySubtract(a1, b);
            }
            if (res.size() || e)
                res.push_back(e + '0');
        }
        ans[0] = res;
        ans[1] = a1;
        return ans;
    }
}
string myFactorial(string a)
{
    if (a == "1" || a == "0")
        return a;
    else
        return myMultiply(a, myFactorial(mySubtract(a, "1")));
}
string myPower(string a, string b)
{
    if (b == "0")
    {
        return "1";
    }
    if (b == "1")
    {
        return a;
    }
    return myMultiply(a, myPower(a, mySubtract(b, "1")));
}
string intDiv(string a, string b)
{
    vector<string> ans = myDivide(a, b);
    return ans[0];
}
string myModulo(string a, string b)
{
    vector<string> ans = myDivide(a, b);
    return ans[1];
}
string FactorialWithoutRecursion(string a)
{
    if (a == "0")
    {
        return "1";
    }
    string b = "1";
    for(string i = "1"; myCompare(i, a) < 1; i = to_string(stoi(i) + 1))
    {
        b = to_string(stoull(b) * stoull(i));
    }
    return b;
}
/*END*/

string x, y;

int main()
{
    cin >> x >> y;
    if((myCompare(x, y) >= 0) || (y.length() > 8))
    {
        cout << 0;
    }
    else
    {
        cout << myModulo(myFactorial(x), y) << endl;
//      cout << myModulo(FactorialWithoutRecursion(x), y) << endl;
//      cout << FactorialWithoutRecursion(x);
    }
    return 0;
}

by cly312 @ 2024-11-29 20:18:49

AI


|