算法打卡 day4
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;
}