题解 | N的阶乘

我们知道数学规律，因此考虑使用动态规划解决本题。

#include <bits/stdc++.h>
#define _CRT_SECURE_NO_WARNINGS

int main() {
    std::vector<long long> product(1001);
    product[0] = 1;
    for (int i = 1; i < 1001; i++) {
        product[i] = product[i - 1] * i;
    }
    int n;
    while (std::cin >> n) {
        std::cout << product[n] << std::endl;
    }
}

然而在实际提交代码后，这段代码测试不通过。在错误的样例中，我们发现这一明显不正确的输出；因此可以判断，就算使用了long long类型，使用简单的乘法处理大数也还是会发生超限。

因此思考其他可以处理大数的方法。显然，字符串的最大长度对应的数一定远超long long类型，因此考虑此方法。和先前竖式思路一样，对大数的每一位进行乘法运算即可。

#include <bits/stdc++.h>
#define _CRT_SECURE_NO_WARNINGS
// 大数加法
std::string addString(std::string a, std::string b)
{
    int carry = 0;
    std::string res;
    int i = a.size() - 1;
    int j = b.size() - 1;
    while (i >= 0 && j >= 0)
    {
        int num = carry + a[i] - '0' + b[j] - '0';
        res += num % 10 + '0';
        carry = num / 10;
        i--;
        j--;
    }
    while (i >= 0)
    {
        int num = carry + a[i] - '0';
        res += num % 10 + '0';
        carry = num / 10;
        i--;
    }
    while (j >= 0)
    {
        int num = carry + b[j] - '0';
        res += num % 10 + '0';
        carry = num / 10;
        j--;
    }
    if (carry > 0)
        res += std::to_string(carry);
    reverse(res.begin(), res.end());
    return res;
}
// 大数乘法(x<=10)
std::string mulString(std::string a, int x)
{
    int carry = 0;
    std::string res;
    for (int i = a.size() - 1; i >= 0; i--)
    {
        int num = carry + (a[i] - '0') * x;
        res += num % 10 + '0';
        carry = num / 10;
    }
    if (carry > 0)
        res += std::to_string(carry);
    reverse(res.begin(), res.end());
    return res;
}
// 组合大数乘法
std::string MulString(std::string a, std::string b)
{
    std::string res;
    for (int i = 0; i < b.size(); i++)
    {
        int x = b[b.size() - 1 - i] - '0';
        std::string num = mulString(a, x);
        for (int j = 0; j < i; j++)
            num = mulString(num, 10);
        res = addString(res, num);
    }
    return res;
}
int main()
{
    int n;
    while (std::cin >> n)
    {
        std::string res = "1";
        for (int i = 2; i <= n; i++)
        {
            res = MulString(res, std::to_string(i));
        }
        std::cout << res << std::endl;
    }
    return 0;
}