怎么样使得这篇代码能够被优化到只需要500MB以下的内存?
查看原帖
怎么样使得这篇代码能够被优化到只需要500MB以下的内存?
1213524
C_plus_plus_12345楼主2024/11/29 20:17
#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;
}
2024/11/29 20:17
加载中...