highPrecisionMultiply 关于那个注释是否添加

P1009 [NOIP1998 普及组] 阶乘之和

xiaozhongnuli @ 2024-05-04 18:24:48

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> highPrecisionAddition(vector<int>& a, vector<int>& b); //高精度加法
void highPrecisionMultiply(vector<int>& a, vector<int>& b, vector<int>& c); //高精度乘法
void factorial(vector<int>& a, int n); //阶乘
void found_array(vector<int>& a, int n);   //容器存储数字

int main()
{
    int n;
    cin >> n;
    vector<int> s;
    vector<int> a;
    vector<int> b;
    vector<int> c = {0};
    for (int i = 0; i < n; i++) {
        if (i == 0) {
            found_array(s, 1);
        }
        else {
            found_array(a, 1);
            for (int j = 2; j < i + 2; j++) {
                found_array(b, j);
                highPrecisionMultiply(a, b, s);
                a = s;
                b.clear();
            }
        }
        c = highPrecisionAddition(s, c);
        s.clear();
        a.clear();
    }
    for (auto it = c.rbegin(); it != c.rend(); ++it) {
        cout << *it;
    }

    return 0;
}

vector<int> highPrecisionAddition(vector<int>& a, vector<int>& b)
{
    int alen = a.size();
    int blen = b.size();
    int len = max(alen, blen);
    vector<int> c;
    c.resize(len+1, 0);
    int i = 0;
    while (i < len) {
        if (a[i] + b[i] >= 10) {
            int d;
            c[i] += a[i] + b[i] - 10;
            ++c[++i];
        }
        else {
            c[i] += a[i] + b[i];
            i++;
        }
    }
    while (c.size() > 1 && c.back() == 0)   c.pop_back();

    return c;
}

void highPrecisionMultiply(vector<int>& a, vector<int>& b, vector<int>& c)
{
    int alen = a.size();
    int blen = b.size();
//  c.clear();
    c.resize(alen * blen + 1, 0);

    for (int i=0; i<alen; i++)
        for (int j = 0; j < blen; j++) {
            if (a[i] * b[j] >= 10) {
                c[i + j] += (a[i] * b[j]) % 10;
                c[i + j + 1] += (a[i] * b[j]) / 10;
            }
            else {
                c[i + j] += a[i] * b[j];
            }
        }
    while (c.back() == 0 && c.size()>1)  c.pop_back();
}

void factorial(vector<int>& a, int n)
{
    int i = 1;
    vector<int> x;
    found_array(x,1);
    vector<int> y;
    while (i < n) {
        ++i;
        found_array(y, i);
        highPrecisionMultiply(x, y, a);
        x = a;
        y.clear();
    }
}

void found_array(vector<int>& a, int n)
{
    a.clear();
    int num;
    while (n > 0) {
        num = n % 10;
        a.push_back(num);
        n /= 10;
    }
}

|