信息学奥赛一本通--基础算法--高精度算法
信息学奥赛一本通基础篇中的高精度算法。
目录
1.高精度乘法
【题目描述】
【输入】
【输出】
【输入样例】
【输出样例】
2.高精度除法
【题目描述】
【输入】
【输出】
【输入样例】
【输出样例】
3.大整数加法
【题目描述】
【输入】
【输出】
【输入样例】
【输出样例】
4.大整数减法
【题目描述】
【输入】
【输出】
【输入样例】
【输出样例】
5.计算2的N次方
【题目描述】
【输入】
【输出】
【输入样例】
【输出样例】
6.大整数的因子
【题目描述】
【输入】
【输出】
【输入样例】
【输出样例】
7.求10000以内n的阶乘
【题目描述】
【输入】
【输出】
【输入样例】
【输出样例】
8.阶乘和
【题目描述】
【输入】
【输出】
【输入样例】
【输出样例】
9.大整数乘法
【题目描述】
【输入】
【输出】
【输入样例】
【输出样例】
10.除以13
【题目描述】
【输入】
【输出】
【输入样例】
【输出样例】
1.高精度乘法
【题目描述】
输入两个高精度正整数M和N（M和N均小于100位）。求这两个高精度数的积。
【输入】
输入两个高精度正整数M和N。
【输出】
求这两个高精度数的积。
【输入样例】
36
3
【输出样例】
108
#include
#include
#include
#include
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>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< 2.高精度除法
【题目描述】
高精除以高精，求它们的商和余数。
【输入】
输入两个低于300位的正整数。
【输出】
输出商和余数。
【输入样例】
1231312318457577687897987642324567864324567876543245671425346756786867867867
1231312318767141738178325678412414124141425346756786867867867
【输出样例】
999999999748590
179780909068307566598992807564736854549985603543237528310337
#include
#include
#include
using namespace std;bool cmp(vector &A, vector &B){if(A.size()!=B.size()) return A.size()>B.size();for(int i=A.size()-1;i>=0;i--){if(A[i]!=B[i]) return A[i]>B[i]; }return true;
}vector sub(vector &A,vector &B){vector C;int t=0;for(int i=0;i1&&C.back()==0) C.pop_back();return C;
}vector div(vector &A, vector &B, vector &r){vector C;int j = B.size();r.assign(A.end()-j,A.end());while(j<=A.size()){int k=0;while(cmp(r,B)){vector s = sub(r,B);r.clear();r.assign(s.begin(),s.end());k++;}C.push_back(k);if(j1&&r.back()==0) r.pop_back();j++;}reverse(C.begin(),C.end());while(C.size()>1&&C.back()==0) C.pop_back();return C;
}int main(){string a,b;cin>>a>>b;vector A,B,r;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');auto C = div(A,B,r);for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);printf("\n");for(int i=r.size()-1;i>=0;i--) printf("%d",r[i]);return 0;
} 3.大整数加法
【题目描述】
求两个不超过200位的非负整数的和。
【输入】
有两行，每行是一个不超过200位的非负整数，可能有多余的前导0。
【输出】
一行，即相加后的结果。结果里不能有多余的前导0，即如果结果是342，那么就不能输出为0342。
【输入样例】
22222222222222222222
33333333333333333333
【输出样例】
55555555555555555555
#include
using namespace std;
vector sum(vector &A,vector &B) {vector C;int t=0;for(int i=0;i A,B;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');auto C=sum(A,B);for(int i=C.size()-1;i>=0;i--) cout< 4.大整数减法
【题目描述】
求两个大的正整数相减的差。
【输入】
共2行，第1行是被减数a，第2行是减数b(a > b)。每个大整数不超过200位，不会有多余的前导零。
【输出】
一行，即所求的差。
【输入样例】
9999999999999999999999999999999999999
9999999999999
【输出样例】
9999999999999999999999990000000000000
#include
using namespace std;
vector solve(vector &A,vector &B) {vector C;int t=0;for(int i=0;i 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 C=solve(A,B);for(int i=C.size()-1;i>=0;i--) cout< 5.计算2的N次方
【题目描述】
任意给定一个正整数N(N<=100)，计算2的n次方的值。
【输入】
输入一个正整数N。
【输出】
输出2的N次方的值。
【输入样例】
5
【输出样例】
32
高精度阶乘的变形。
#include
using namespace std;
int n;
void solve() {vector c;c.push_back(1);for(int i=1;i<=n;i++) {int t=0;for(int j=0;j=0;i--) cout<>n;solve();return 0;
} 6.大整数的因子
【题目描述】
已知正整数k满足2≤k≤9，现给出长度最大为30位的十进制非负整数c，求所有能整除c的k。
【输入】
一个非负整数c，c的位数≤30。
【输出】
若存在满足 c%k == 0 的k，从小到大输出所有这样的k，相邻两个数之间用单个空格隔开；若没有这样的k，则输出"none"。
【输入样例】
30
【输出样例】
2 3 5 6
#include
using namespace std;
vector A;
void solve(vector &A,int B,int &r) {vector C;for(int i=0;i1&&C.back()==0) C.pop_back();*/
}
signed main() {string a;cin>>a;vector A;for(int i=0;i C=A;bool flag=false;for(int i=2;i<=9;i++) {int r=0;solve(A,i,r);A=C;if(r==0) {flag=true;cout< 7.求10000以内n的阶乘
【题目描述】
求10000以内n的阶乘。
【输入】
只有一行输入，整数n（0≤n≤10000）。
【输出】
一行，即n!的值。
【输入样例】
4
【输出样例】
24
#include
#define int long long
using namespace std;
int n;
void solve() {cin>>n;vector c;c.push_back(1);for(int i=1;i<=n;i++) {int t=0;for(int j=0;j=0;i--) cout< 8.阶乘和
【题目描述】
用高精度计算出S=1!+2!+3!+…+n!（n≤100）,其中“!”表示阶乘，例如：5!=5×4×3×2×1。
输入正整数n，输出计算结果S。
【输入】
一个正整数n。
【输出】
计算结果S。
【输入样例】
5
【输出样例】
153
#include
#define int long long
using namespace std;
const int N=1e6+10;
int n;
vector f(int n) {vector v;v.push_back(1);for(int i=1;i<=n;i++) {int t=0;for(int j=0;j sum(vector &A,vector &B) {vector C;int t=0;for(int i=0;i>n;vector ans;for(int i=1;i<=n;i++) {auto x=f(i);ans=sum(ans,x);}for(int i=ans.size()-1;i>=0;i--) {cout< 9.大整数乘法
【题目描述】
求两个不超过200位的非负整数的积。
【输入】
有两行，每行是一个不超过200位的非负整数，没有多余的前导0。
【输出】
一行，即相乘后的结果。结果里不能有多余的前导0，即如果结果是342，那么就不能输出为0342。
【输入样例】
12345678900
98765432100
【输出样例】
1219326311126352690000
#include
#include
#include
#include
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>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< 10.除以13
【题目描述】
输入一个大于0的大整数N，长度不超过100位，要求输出其除以13得到的商和余数。
【输入】
一个大于0的大整数，长度不超过100位。
【输出】
两行，分别为整数除法得到的商和余数。
【输入样例】
2132104848488485
【输出样例】
164008065268345
0
#include
using namespace std;
vector A;
void solve(vector &A,int B,int &r) {vector C;for(int i=0;i1&&C.back()==0) C.pop_back();for(int i=C.size()-1;i>=0;i--) cout<>a;vector A;for(int i=0;i
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！