4 . 高精度算法
性质：数组或者容器从低位往高位依次存储大整数，方便进位。
4.1 高精度加法
给定两个正整数（不含前导 0），计算它们的和。
输入格式
共两行，每行包含一个整数。
输出格式
共一行，包含所求的和。
数据范围
1≤整数长度≤100000
输入样例：
12
23
输出样例：
35
思路：
模拟人工加法。
//高精度 加法
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
vector<int> sum(vector<int> &A,vector<int> &B)
{
vector<int> C;
int k = 0;
for(int i = 0;i < max(A.size(),B.size());i++)
{
if(i<A.size()) k+=A[i];
if(i<B.size()) k+=B[i];
C.push_back(k%10);
k/=10;
}
if(k) C.push_back(1);
return C;
}
int main()
{
string a,b;
vector<int> A,B;
cin>>a>>b;
for(int i = a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
for(int i = b.size()-1;i>=0;i--) B.push_back(a[i]-'0');
vector<int> C=sum(A,B);
for(int i=C.size()-1;i>=0;i--) cout<<C[i];
return 0;
}4.2 高精度减法
给定两个正整数（不含前导 0），计算它们的差，计算结果可能为负数。
输入格式
共两行，每行包含一个整数。
输出格式
共一行，包含所求的差。
数据范围
1≤整数长度≤105
输入样例：
32
11
输出样例：
21
思路：
模拟人工减法。
#include <bits/stdc++.h>
using namespace std;
vector<int> A,B;
bool cmp(vector<int> &A,vector<int> &B){
if(A.size()!=B.size()) return A.size()>B.size();
else{
for(int i=A.size()-1;i>=0;i--){
if(A[i]!=B[i]) return A[i]>B[i];
}
}
return 1;
}
vector<int> sub(vector<int> &A,vector<int> &B){
int k=0;//表示上一位在这一位借走的位数
vector<int> C;
for(int i=0;i<A.size();i++){
int t=A[i]-k;
if(i<B.size()) t-=B[i];
if(t<0) t+=10,k=1;
else k=0;
C.push_back(t%10);
}
while(C.size()>1&&C.back()==0) C.pop_back();
return C;
}
int main(){
string a,b;
cin>>a>>b;
for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
for(int i=b.size()-1;i>=0;i--) B.push_back(b[i]-'0');
vector<int> C;
if(cmp(A,B)) C=sub(A,B); //当A>=B时，答案为0或正值
else C=sub(B,A),cout<<"-"; //当A<B时，答案为负值
for(int i=C.size()-1;i>=0;i--) cout<<C[i];
return 0;
}4.3 高精度乘法
给定两个非负整数（不含前导 0)A 和 B，请你计算 A×B 的值。
输入格式
共两行，第一行包含整数 A，第二行包含整数 B。
输出格式
共一行，包含 A×B 的值。
数据范围
1≤A的长度≤100000,
0≤B≤10000
输入样例：
2
3
输出样例：
6
高精度x低精度
高精度x高精度
//高精度x低精度
#include<bits/stdc++.h>
#include<vector>
using namespace std;
vector<int> mul(vector<int> &A,int b)
{
vector<int> C;
int t=0;
for(int i=0;i<A.size();i++)
{
t+=A[i]*b;
C.push_back(t%10);
t/=10;
}
while(t)
{
C.push_back(t%10);
t/=10;
}
while(C.size()>1&&C.back()==0) C.pop_back();
return C;
}
int main()
{
string a;
int b;
cin>>a>>b;
vector<int> A;
for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
auto C=mul(A,b);
for(int i=C.size()-1;i>=0;i--) cout<<C[i];
return 0;
}//高精度 x 高精度
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 1e5+10;
int A[N],B[N],C[N];
int la,lb,lc;
void mul(int A[],int B[],int C[])
{
for(int i=0;i<la;i++)
for(int j=0;j<lb;j++)
{
C[i+j]+=A[i]*B[j];
C[i+j+1]+=C[i+j]/10;
C[i+j]%=10;
}
while(lc&&C[lc]==0) lc--;
}
int main()
{
string a,b;
cin>>a>>b;
la=a.size();
lb=b.size();
lc=la+lb+10;
for(int i=a.size()-1;i>=0;i--) A[la-i-1]=a[i]-'0';
for(int i=b.size()-1;i>=0;i--) B[lb-i-1]=b[i]-'0';
mul(A,B,C);
for(int i=lc;i>=0;i--) cout<<C[i];
return 0;
}4.4 高精度除法
给定两个非负整数（不含前导 0)A，B，请你计算 A/B的商和余数。
输入格式
共两行，第一行包含整数 A，第二行包含整数 B。
输出格式
共两行，第一行输出所求的商，第二行输出所求余数。
数据范围
1≤A的长度≤100000,
1≤B≤10000,
B 一定不为 00
输入样例：
7
2
输出样例：
3
1
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> div(vector<int> &A,int B,int &r)
{
vector<int> C;
for(int i=0;i<A.size();i++)
{
r=r*10+A[i];
C.push_back(r/B);
r%=B;
}
reverse(C.begin(),C.end());
while(C.size()>1&&C.back()==0) C.pop_back();
return C;
}
int main()
{
string a;
int B,r=0;
cin>>a>>B;
vector<int> A;
for(int i=0;i<a.size();i++) A.push_back(a[i]-'0');
auto C=div(A,B,r);
for(int i=C.size()-1;i>=0;i--) cout<<C[i];
cout<<endl<<r;// 输出余数
return 0;
}4.5 高精度阶乘
问题描述
输入一个正整数n，输出n!的值。
其中n!=1*2*3*…*n。
算法描述
n!可能很大，而计算机能表示的整数范围有限，需要使用高精度计算的方法。使用一个数组A来表示一个大整数a，A[0]表示a的个位，A[1]表示a的十位，依次类推。
将a乘以一个整数k变为将数组A的每一个元素都乘以k，请注意处理相应的进位。
首先将a设为1，然后乘2，乘3，当乘到n时，即得到了n!的值。
输入格式
输入包含一个正整数n，n<=1000。
输出格式
输出n!的准确值。
样例输入
10
样例输出
3628800
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+10;
int n;
int a[N];
int main()
{
scanf("%d",&n);
a[1]=1;
int t=0;
for(int i=2;i<=n;i++)
{
for(int j=1;j<=10000;j++)
{
int p=a[j]*i+t;
a[j]=p%10;
t=p/10;
}
}
n=10000;
while(a[n]==0) n--;
for(int i=n;i>=1;i--) cout<<a[i];
return 0;
}