高精度算法总结

一句话：只需将两个大数按照竖式模拟计算即可！

高精度加法：

题解报告：hdu 1002 A + B Problem II

Problem Description

I have a very simple problem for you. Given two integers A and B, your job is to calculate the Sum of A + B.

Input

The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line consists of two positive integers, A and B. Notice that the integers are very large, that means you should not process them by using 32-bit integer. You may assume the length of each integer will not exceed 1000.

Output

For each test case, you should output two lines. The first line is "Case #:", # means the number of the test case. The second line is the an equation "A + B = Sum", Sum means the result of A + B. Note there are some spaces int the equation. Output a blank line between two test cases.

Sample Input

1 2

112233445566778899 998877665544332211

Sample Output

Case 1:

1 + 2 = 3

Case 2:

112233445566778899 + 998877665544332211 = 1111111111111111110

解题思路：大数加法，简单模拟竖式运算或者直接调用java中BigInteger大数类的add()方法即可。

AC之C++代码：时间复杂度为O(n)。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <cmath>
 5 #include <iostream>
 6 #include <algorithm>
 7 #include <iomanip>
 8 #include <complex>
 9 #include <string>
10 #include <vector>
11 #include <set>
12 #include <map>
13 #include <list>
14 #include <deque>
15 #include <queue>
16 #include <stack>
17 using namespace std;
18 typedef long long LL;
19 typedef unsigned long long ULL;
20 const double eps = 1e-6;
21 const double PI = acos(-1.0);
22 const int maxn = 1e5+5;
23 const int inf = 0x3f3f3f3f;
24 
25 int t, now, tmp;
26 string a, b, r;
27 bool flag;
28 
29 int main(){
30     while(cin >> t){
31         flag = true;
32         for(int i = 1; i <= t; ++i){
33             cin >> a >> b;
34             tmp = 0, r = "";
35             if(!flag) puts("");
36             cout << "Case " << i << ":
" << a << " + " << b << " = ";
37             if(a.size() > b.size()) swap(a, b);
38             for(int i = a.size() - 1, j = b.size() - 1; ~j; --i, --j){
39                 now = (i >= 0 ? a[i] - '0' : 0) + b[j] - '0' + tmp;
40                 tmp = now > 9 ? 1 : 0;
41                 now = now > 9 ? now - 10 : now;
42                 r += '0' + now;
43             }
44             if(tmp) r += '1'; //如果还有进位，则高位补1
45             for(int i = r.size() - 1; ~i; --i) cout << r[i];
46             puts(""); flag = false;
47         }
48     }
49     return 0;
50 }

View Code

AC之java代码：

 1 import java.util.Scanner;
 2 import java.math.BigInteger;
 3 public class Main {
 4     public static void main(String[] args) {
 5         Scanner scan = new Scanner(System.in);
 6         int t = scan.nextInt();
 7         BigInteger a, b;
 8         for(int i = 1; i <= t; ++i){
 9             a = scan.nextBigInteger();
10             b = scan.nextBigInteger();
11             System.out.println("Case " + i + ":");
12             System.out.println(a + " + " + b + " = " + a.add(b));
13             if(i != t) System.out.println();
14         }    
15     }
16 }

View Code

高精度乘法：

蓝桥杯算法提高 P1001

时间限制：1.0s 内存限制：256.0MB

当两个比较大的整数相乘时，可能会出现数据溢出的情形。为避免溢出，可以采用字符串的方法来实现两个大数之间的乘法。具体来说，首先以字符串的形式输入两个整数，每个整数的长度不会超过8位，然后把它们相乘的结果存储在另一个字符串当中（长度不会超过16位），最后把这个字符串打印出来。例如，假设用户输入为：62773417和12345678，则输出结果为：774980393241726.
输入：
62773417 12345678
输出：
774980393241726

注意：特判输入有0的情况！

AC之C++代码：时间复杂度为O(n^2)。此方法适用于两个位数不大的大数做乘法运算。（没有做压位运算）

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <cmath>
 5 #include <iostream>
 6 #include <algorithm>
 7 #include <iomanip>
 8 #include <complex>
 9 #include <string>
10 #include <vector>
11 #include <set>
12 #include <map>
13 #include <list>
14 #include <deque>
15 #include <queue>
16 #include <stack>
17 using namespace std;
18 typedef long long LL;
19 typedef unsigned long long ULL;
20 const double eps = 1e-6;
21 const double PI = acos(-1.0);
22 const int maxn = 10;
23 const int inf = 0x3f3f3f3f;
24 
25 char s1[maxn], s2[maxn];
26 int m1, m2, a[maxn], b[maxn], carry, ans[maxn << 1]; //2倍
27 bool flag;
28 
29 int main() {
30     while(cin >> s1 >> s2) {
31         memset(ans, 0, sizeof(ans));
32         memset(a, 0, sizeof(a));
33         memset(b, 0, sizeof(b));
34         m1 = strlen(s1), m2 = strlen(s2), carry = 0;
35         if((m1 == 1 && s1[0] == '0') || (m2 == 1 && s2[0] == '0')) {puts("0"); continue;} //特判0
36         for(int i = m1 - 1; ~i; --i) a[m1 - 1 - i] = s1[i] - '0';
37         for(int i = m2 - 1; ~i; --i) b[m2 - 1 - i] = s2[i] - '0';
38         for(int i = 0; i < m2; ++i) {
39             for(int j = 0; j < m1; ++j) {
40                 ans[j + i] += a[j] * b[i] + carry;
41                 if(ans[j + i] > 9) carry = ans[j + i] / 10, ans[j + i] %= 10;
42                 else carry = 0;
43             }
44             if(carry) ans[i + m1] += carry, carry = 0;
45         }
46         flag = false;
47         for(int i = m1 + m2 - 1; ~i; --i) { //最多有m1 + m2位数
48             if(!flag && !ans[i]) continue;
49             flag = true;
50             cout << ans[i];
51         }
52         puts("");
53     }
54     return 0;
55 }

View Code

AC之java代码：

 1 import java.util.Scanner;
 2 import java.math.BigInteger;
 3 public class Main {
 4     public static void main(String[] args){
 5         Scanner scan = new Scanner(System.in);
 6         BigInteger a, b;
 7         while(scan.hasNext()) {
 8             a = scan.nextBigInteger();
 9             b = scan.nextBigInteger();
10             System.out.println(a.multiply(b));
11         }
12     }
13 }

View Code

题解报告：hdu 1042 N!

Problem Description

Given an integer N(0 ≤ N ≤ 10000), your task is to calculate N!

Input

One N in one line, process to the end of file.

Output

For each N, output N! in one line.

Sample Input

1 2 3

Sample Output

1 2 6

AC之C++代码：高精度乘法压5位。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <cmath>
 5 #include <iostream>
 6 #include <algorithm>
 7 #include <iomanip>
 8 #include <complex>
 9 #include <string>
10 #include <vector>
11 #include <set>
12 #include <map>
13 #include <list>
14 #include <deque>
15 #include <queue>
16 #include <stack>
17 using namespace std;
18 typedef long long LL;
19 typedef unsigned long long ULL;
20 const double eps = 1e-6;
21 const double PI = acos(-1.0);
22 const int maxn = 7200; // log_10^(10000!) ≈ 35560，压5位，则最多存35560 / 5 约等于7200
23 const int inf = 0x3f3f3f3f;
24 
25 int n, cnt, carry, ans[maxn];
26 
27 int main() {
28     while(cin >> n) {
29         memset(ans, 0, sizeof(ans));
30         cnt = carry = 0;
31         ans[cnt++] = 1;
32         for(int i = 2; i <= n; ++i) {
33             for(int j = 0; j < cnt; ++j) {
34                 ans[j] = ans[j] * i + carry; // 先乘再累加进位
35                 if(ans[j] > 99999) carry = ans[j] / 100000, ans[j] %= 100000;
36                 else carry = 0;
37             }
38             if(carry) ans[cnt++] = carry, carry = 0; //放到下一位，同时进位置0
39         }
40         printf("%d", ans[cnt - 1]); //先输出最高位，余下五位五位输出
41         for(int j = cnt - 2; j >= 0; --j)
42             printf("%05d", ans[j]); // 不足补0
43         puts("");
44     }
45     return 0;
46 }

View Code

高精度减法：

luogu P2142 高精度减法

题目描述

高精度减法

输入格式：
两个整数a,b（第二个可能比第一个大）

输出格式：
结果（是负数要输出负号）

输入输出样例
输入样例#1：
2
1
输出样例#1：
1
说明
20%数据a,b在long long范围内
100%数据0<a,b<=10的10000次方

AC之C++代码：时间复杂度是O(n)。注意：做减法时，被减数要大于减数！！！

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <cmath>
 5 #include <iostream>
 6 #include <algorithm>
 7 #include <iomanip>
 8 #include <complex>
 9 #include <string>
10 #include <vector>
11 #include <set>
12 #include <map>
13 #include <list>
14 #include <deque>
15 #include <queue>
16 #include <stack>
17 using namespace std;
18 typedef long long LL;
19 typedef unsigned long long ULL;
20 const double eps = 1e-6;
21 const double PI = acos(-1.0);
22 const int maxn = 1e4+5;
23 const int inf = 0x3f3f3f3f;
24 
25 char s1[maxn], s2[maxn];
26 int m1, m2, maxL, a[maxn], b[maxn], ans[maxn];
27 bool op1, op2, flag;
28 
29 int main() {
30     while(cin >> s1 >> s2) {
31         memset(a, 0, sizeof(a));
32         memset(b, 0, sizeof(b));
33         memset(ans, 0, sizeof(ans));
34         if(!strcmp(s1, s2)) {puts("0"); continue;}
35         op1 = (s1[0] == '-') ? true : false;
36         op2 = (s2[0] == '-') ? true : false;
37         m1 = strlen(s1), m2 = strlen(s2);
38         for(int i = op1 ? 1 : 0, k = op1 ? 0 : 1; i < m1; ++i) a[i - !k] = (s1[m1 - k - i] - '0');
39         for(int i = op2 ? 1 : 0, k = op2 ? 0 : 1; i < m2; ++i) b[i - !k] = (s2[m2 - k - i] - '0');
40         maxL = max(m1, m2);
41         if((op1 && !op2) || (!op1 && op2)) { // 负、正 --> 负；正、负 --> 正
42             if(op1 && !op2) cout << '-';
43             for(int j = 0; j < maxL; ++j) { //加法运算
44                 ans[j] += a[j] + b[j];
45                 ans[j + 1] += ans[j] > 9 ? 1 : 0; //进位
46                 ans[j] = ans[j] > 9 ? ans[j] - 10 : ans[j];
47             }
48         }
49         else {
50             if(!op1) {
51                 if(m1 < m2 || (m1 == m2 && strcmp(s1, s2) < 0)) cout << '-', swap(a, b); //正、正 --> 正，交换
52             }
53             else if(op2) {
54                 if(m1 > m2 || (m1 == m2 && strcmp(s1, s2) > 0)) cout << '-'; //负、负 --> s1 > s2 -- > 负数，不交换
55                 else swap(a, b);
56             }
57             for(int j = 0; j < maxL; ++j) { //减法运算
58                 if(a[j] < b[j]) a[j + 1]--, a[j] += 10; //借位
59                 ans[j] = a[j] - b[j];
60             }
61         }
62         flag = false;
63         for(int j = maxL; ~j; --j) { //多处理一个进位项的系数
64             if(!flag && !ans[j]) continue; //去掉前导0
65             flag = true;
66             cout << ans[j];
67         }
68         puts("");
69     }
70     return 0;
71 }

View Code

AC之java代码：

 1 import java.util.Scanner;
 2 import java.math.BigInteger;
 3 public class Main {
 4     public static void main(String[] args){
 5         Scanner scan = new Scanner(System.in);
 6         BigInteger a, b;
 7         while(scan.hasNext()) {
 8             a = scan.nextBigInteger();
 9             b = scan.nextBigInteger();
10             System.out.println(a.subtract(b));
11         }
12     }
13 }

View Code