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;
}
