第二部分 基础算法 --> 第一章 高精度计算
目录
- 高精度算法
- 1168：大整数加法
- 1169：大整数减法
- 1174：大整数乘法
- 1307：【例1.3】高精度乘法
- 1170：计算2的N次方
- 1172：求10000以内n的阶乘
- 1175：除以13
- 1308：【例1.5】高精除
高精度算法
1168：大整数加法
【题目描述】
求两个不超过200位的非负整数的和。
【输入】
有两行，每行是一个不超过200位的非负整数，可能有多余的前导0。
【输出】
一行，即相加后的结果。
结果里不能有多余的前导0，即如果结果是342，那么就不能输出为0342。
【输入样例】
22222222222222222222
33333333333333333333
【输出样例】
55555555555555555555
【参考程序】
#include
#include
#include
#include
using namespace std;
const int N=1e6;
int A[N], B[N], C[N], la, lb, lc;
//初始化
void init(string a, string b){
memset(A, 0, sizeof(A));
memset(B, 0, sizeof(B));
memset(C, 0, sizeof(C));
la=a.length(), lb=b.length();
for(int i=0; i9){
C[i+1]=C[i]/10, C[i]%=10;
}
}
while(C[lc]) lc++;
string c;
for(int i=lc-1; i>=0; i--) c.append(1, C[i]+'0');
return c;
}
//去除多余前导0
string rem(string a){
char s[1001];
int len=a.length(), p=0;
for(int i=0; i>a>>b;
a=rem(a), b=rem(b);
cout< 1169：大整数减法
【题目描述】
求两个大的正整数相减的差。
【输入】
共2行，第1行是被减数a，第2行是减数b(a > b)。
每个大整数不超过200位，不会有多余的前导零。
【输出】
一行，即所求的差。
【输入样例】
9999999999999999999999999999999999999
9999999999999
【输出样例】
9999999999999999999999990000000000000
【参考程序】
#include
#include
#include
#include
using namespace std;
const int N=1e6;
int A[N], B[N], C[N], la, lb, lc;
//初始化
void init(string a, string b){
memset(A, 0, sizeof(A));
memset(B, 0, sizeof(B));
memset(C, 0, sizeof(C));
la=a.length(), lb=b.length();
for(int i=0; i1 && C[lc-1]==0) lc--;//去除前导 0
string c;
for(int i=lc-1; i>=0; i--) c.append(1, C[i]+'0');
return c;
}
int main() {
string a,b; cin>>a>>b;
if(a 1174：大整数乘法
【题目描述】
求两个不超过200位的非负整数的积。
【输入】
有两行，每行是一个不超过200位的非负整数，没有多余的前导0。
【输出】
一行，即相乘后的结果。结果里不能有多余的前导0，即如果结果是342，那么就不能输出为0342。
【输入样例】
12345678900
98765432100
【输出样例】
1219326311126352690000
【参考程序】
#include
#include
#include
#include
using namespace std;
const int N=1e6;
int A[N], B[N], C[N], la, lb, lc;
void init(string a, string b){
memset(A, 0, sizeof(A));
memset(B, 0, sizeof(B));
memset(C, 0, sizeof(C));
la=a.length(), lb=b.length();
for(int i=0; i9){
C[i+1] += C[i]/10, C[i]%=10;
}
}
while(C[lc]) lc++;
string c;
for(int i=lc-1; i>=0; i--) c.append(1, C[i]+'0');
return c;
}
int main() {
string a,b;
while(cin>>a>>b){
cout< 1307：【例1.3】高精度乘法
【题目描述】
输入两个高精度正整数M和N（M和N均小于100位）。
求这两个高精度数的积。
【输入】
输入两个高精度正整数M和N。
【输出】
求这两个高精度数的积。
【输入样例】
36
3
【输出样例】
108
【参考程序】
#include
#include
#include
#include
using namespace std;
const int N=1e6;
int A[N], B[N], C[N], la, lb, lc;
//初始化
void init(string a, string b){
memset(A, 0, sizeof(A));
memset(B, 0, sizeof(B));
memset(C, 0, sizeof(C));
la=a.length(), lb=b.length();
for(int i=0; i9){
C[i+1] += C[i]/10, C[i]%=10;
}
}
while(C[lc]) lc++;
while(lc>1&&C[lc-1]==0) lc--;//去除前导 0, 10*0=0
string c="";
for(int i=lc-1; i>=0; i--) c.append(1, C[i]+'0');
return c;
}
int main() {
string a, b; cin>>a>>b;
cout< 1170：计算2的N次方
【题目描述】
任意给定一个正整数N(N<=100)，计算2的n次方的值。
【输入】
输入一个正整数N。
【输出】
输出2的N次方的值。
【输入样例】
5
【输出样例】
32
【参考程序1】
#include
#include
#include
#include
using namespace std;
const int N=1e6;
int A[N], B[N], C[N], la, lb, lc;
void init(string a, string b){
memset(A, 0, sizeof(A));
memset(B, 0, sizeof(B));
memset(C, 0, sizeof(C));
la=a.length(), lb=b.length();
for(int i=0; i9){
C[i+1] += C[i]/10, C[i]%=10;
}
}
while(C[lc]) lc++;
string c;
for(int i=lc-1; i>=0; i--) c.append(1, C[i]+'0');
return c;
}
int main() {
int n; cin>>n;
string a="1",b="2";
for(int i=1; i<=n; i++){
a = mul(a, b);
}
cout< 1172：求10000以内n的阶乘
【题目描述】
求10000以内n的阶乘。
【输入】
只有一行输入，整数n（0≤n≤10000）。
【输出】
一行，即n!的值。
【输入样例】
4
【输出样例】
24
此题数据较严格，如果单纯如下参考程序1，会被卡时间
1e3*（3e4）^2 > 1e9 游戏结束
【参考程序1】
#include
#include
#include
#include
using namespace std;
const int N=1e6;
int A[N], B[N], C[N], la, lb, lc;
//初始化
void init(string a, string b){
memset(A, 0, sizeof(A));
memset(B, 0, sizeof(B));
memset(C, 0, sizeof(C));
la=a.length(), lb=b.length();
for(int i=0; i9){
C[i+1] += C[i]/10, C[i]%=10;
}
}
while(C[lc]) lc++;
while(lc>1&&C[lc-1]==0) lc--;//去除前导 0, 10*0=0
string c="";
for(int i=lc-1; i>=0; i--) c.append(1, C[i]+'0');
return c;
}
//整数转string
string tos(int n){
char s[1001];
int cnt=0;
while(n){
s[cnt++]=n%10+'0';
n/=10;
}
s[cnt]='\0';
reverse(s, s+cnt);
string a=""; a.append(s);
return a;
}
int main() {
int n; cin>>n;
string a="1";
for(int i=1; i<=n; i++){
a = mul(a, tos(i));
}
cout< 【参考程序2】
#include
using namespace std;
const int N =1e6;
int a[N]={0, 1};
int main(){
int n, l=1; scanf("%d", &n);
for(int i=1; i<=n; i++){
for(int j=1; j<=l; j++){
a[j] = a[j]*i;
a[j] += a[j-1]/10;
a[j-1] %= 10;
if(a[j]>9 && j==l) l++;
}
}
for(int i=l; i>=1; i--) printf("%d", a[i]);
return 0;
}
1175：除以13
【题目描述】
输入一个大于0的大整数N，长度不超过100位，要求输出其除以13得到的商和余数。
【输入】
一个大于0的大整数，长度不超过100位。
【输出】
两行，分别为整数除法得到的商和余数。
【输入样例】
2132104848488485
【输出样例】
164008065268345
0
【参考程序】
1308：【例1.5】高精除
【题目描述】
高精除以高精，求它们的商和余数。
【输入】
输入两个低于300位的正整数。
【输出】
输出商和余数。
【输入样例】
1231312318457577687897987642324567864324567876543245671425346756786867867867
1231312318767141738178325678412414124141425346756786867867867
【输出样例】
999999999748590
179780909068307566598992807564736854549985603543237528310337
【参考程序】