【C++】阶乘相加问题

洛谷原题 https://www.luogu.com.cn/problem/P1009
洛谷这道题目要求用高精度写阶乘，但是我还没有学过。从网上扒各种资料和网课，发现在学习高精度之前，需要知道vector这个容器。

vector是一个封装了动态大小数组的顺序容器，属于C++STL。可以简单认为。vector是一个能够存放任意类型的动态数组。

使用vector需要在文件开头加上
#include< vector >
using namespace std;

原文链接：https://blog.csdn.net/qq_38654981/article/details/81907134
https://blog.csdn.net/w_linux/article/details/71600574
vector的初始化：

1. vector<类型>标识符 //vector a
2. vector<类型>标识符(最大容量) //vectora(10)
3. vector<类型>标识符(最大容量,初始所有值) //vectora(10,1)
4. int b[7]={1,2,3,4,5,9,8}; vector a(b,b+7); //从数组中获得初值
5. vector< vector< int> >v; 二维向量 //这里最外的<>要有空格。否则在比较旧的编译器下无法通过
6. vector a(b); //用b向量来创建a向量，整体复制性赋值

vector函数合集
https://blog.csdn.net/w_linux/article/details/71600574

学完vector后开始学习高精度计算

高精度计算实际上就是将大数据存储到字符串中，手动进行运算和重新储存。其原理大致相同，算法不同。

#include 
//自带一个size函数求长度 
#include  
using namespace std;
//数组长度+10防止边界问题 
const int N=1e6+10;
//写一个方法返回vector类型 
//这里取地址符是因为引用类型更快 
//C=A+B
vector add(vector &A,vector &B){
	vector C;
	int t =0;//这是进位，同时用来存放数据 
	for (int i=0;iA,B;
	cin>>a>>b; //a="123456"
	for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');
	//倒序存储//字符变整数减去'0' 
	for(int i=b.size()-1;i>=0;i--)B.push_back(b[i]-'0');
	auto C = add(A,B);
	//逆序输出 
	for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);
	return 0; 
}

高精度减法与加法在main函数中主要是输入和输出，没有什么差别，所以为了方便，只放入函数模板片段。

vector sub(vector &A, vector &B)
{
    vector C;
    for (int i = 0, t = 0; i < A.size(); i ++ )
    {   //t用来存放数据
        t = A[i] - t; //可能前面有借位
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);//t+10 因为t-B[i]后有可能是负数
        //如果t<0则记录，向高位借1: 回到 t=A[i]-t t=1时，高位数字减少1
        if (t < 0) t = 1;
        else t = 0;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();//判断最高位是否为0
    return C;
}

高精度乘法和平时做的乘法式子有区别，平时我们做乘法是，比如123*12，是123*2+123*10。
而高精度乘法的，比如123*12
3*12=36，进位3，最后一位为6。
2*12+3=27，进位2倒数第二位为7。
1*12+2=14，进位1，倒数第三位是4。
0*12+1=1，第一位是1。
组合起来为1476。

代码实现如下：

#include 
//自带一个size函数求长度
#include 
using namespace std;
//数组长度+10防止边界问题
const int N=1e6+10;
//写一个方法返回vector类型
//这里取地址符是因为引用类型更快
vector mul(vector &A,int b)
{
    vector C;
    if (b==0){ //因为是字符串类型，不加if判断会导致在*0时输出00000
        C.push_back(0);
        return C;
    }
    int t =0;
    for (int i =0;i A;
    cin>>a>>b;
    //从低位开始存入
    for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
    auto C = mul(A,b);
    //从vector末尾开始输出
    for(int i =C.size()-1;i>=0;i--) printf("%d",C[i]);
    return 0;
}

mul函数部分可以简化如下：

vector mul(vector &A,int b)
{
    vector C;
    if (b==0){ //同样，0数据需要特判
        C.push_back(0);
        return C;
    }
    int t =0;
    for (int i =0;i 
高精度除低精度 
思路整理：
 138/12
 从最高位开始1/12=0…1，1掉到下一位
 上式余数*10+第二位：(1*10+3)/12=1…1，1到下一位
 同理得：(1*10+8)/12=1…6
 得到答案011，去掉最高位0，答案为11…6
 
除法除了返回商，还会返回余数：
 代码实现如下：
 
#include 
//自带一个size函数求长度
#include 
#include   //这个头文件包含函数reverse
using namespace std;
//数组长度+10防止边界问题
const int N=1e6+10;
//写一个方法返回vector类型
//这里取地址符是因为引用类型更快
vector div(vector &A,int b,int &r)//r是余数,用了取地址符，直接改变r的值
{
    vector C;
    r=0;
    for(int i=A.size()-1;i>=0;i--){   //除法需要从高位数开始除，所以for是正着循环
        r=r*10+A[i];
        C.push_back(r/b);
        r=(r%b);
    }
    reverse(C.begin(),C.end());  //因为C最后得到的结果是正序的，而C输出是倒序，所以要反过来
    while (C.size()>1&& C.back()==0) C.pop_back(); //去除前导0  这句话需要放在reverse后面！
    return C;
}
int main(){
    //a数字太长，用字符串读取，b可直接读入
    string a;
    int b,r;
    //将a存入vector
    vector A;
    cin>>a>>b;
    //从低位开始存入
    for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
    auto C = div(A,b,r);
    //从vector末尾开始输出
    for(int i =C.size()-1;i>=0;i--) printf("%d",C[i]);
    cout< 
其实高精度计算的输入输出部分都差不了太多，主要在于函数模板那一块
 
特别注意，高精度除法需要在函数中设置余数。
 
阶乘相加的实现代码：
 输入：3
 输出：3！+2！+1！=9
 
#include 
#include 

using namespace std;

int main() {
    int n;
    cin >> n;
    vector A, B;
    int t = 0;int te=0;
    A.push_back(1);B.push_back(1);
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j < A.size() + 2;) {
            A[j] = i * A[j] + t;
            t = A[j] / 10;
            if (A[j] >= 10)A[j] = A[j] % 10;
            j++;
            if (j >= A.size() && t != 0) {
                while (1) {
                    if (t != 0) {
                        A.push_back(t % 10);
                        t /= 10;
                    } else break;
                }
                break;
            }
            if (j == A.size() && t == 0) break;
        }
        for (int i=0;iB.size()-1) {
                B.push_back((A[i]+te)%10);te=(A[i]+te)/10;
                continue;
            }
        }
    }
    for (int i = B.size() - 1; i >= 0; i--) printf("%d", B[i]);
    return 0;
}