高精度算法

• 前言
• 大数加法
• • 不可以处理负数的模板
  • 可以处理负数
• 大数减法
• • 两个数都是整数，且相减结果大于0
  • 两个数都是正整数，相减结果可以是负数
  • 两个数均可以是负数
• 高精度乘法
• • 两个数均可以是负数
• 大数除法
• • 两个数均可以是负数
• 大数取模

前言

不得不说csdn上面的文章是越来越乱了，搞的想骂人的那种。本文在这里声明，这是一篇模板的博客，如果向更深入的了解（会提及一些）可以去参考别的文章。没一个模板都经过博主简化和模块化已达到易写的目的。

大数加法

不可以处理负数的模板

// C = A + B, A >= 0, B >= 0vector<int> add(vector<int> &A, vector<int> &B){    if (A.size() < B.size()) return add(B, A);    vector<int> C;    int t = 0;    for (int i = 0; i < A.size(); i ++ )    { t += A[i]; if (i < B.size()) t += B[i]; C.push_back(t % 10); t /= 10;    }    if (t) C.push_back(t);    return C;}

可以处理负数

因为减法就是带负数的加法，因此我们在处理负数的时候一般是对负数的情况进行讨论

#include #include #include #include #include using namespace std;char a[1000005];char b[1000005];int fa, fb;int la, lb;void show(int ed) {if (fa)printf("-");for (int i = ed; i >= fa; --i)printf("%d", a[i]);}// 两个都为负数或者两个都不是负数的情况void add() {int i, j, t = 0, s, l;for (i = fa; i < la || i < lb; ++i) {s = a[i]  + b[i]   + t;t = s / 10;a[i] = s % 10;}a[i] = t ;l = t ? i : i - 1;//t是进位 ，如果最后进位了，这l为i，否则只到i-1show(l);}//比较大小int cmp() {int la = strlen(a), lb = strlen(b);if (la - fa > lb - fb) // 比较长度return 1;else if (la - fa < lb - fb)return 0;else {// 长度相等则看每一位int i ;for ( i = 0; i < la && a[i + fa] == b[i + fb]; ++i);return a[i + fa] > b[i + fb];}}void minu() {//两个符号不一样的话是利用减法int i, j, c = 0, l = -1, s;for (i = 0; i + fa < la; ++i) {s = a[i + fa] - b[i + fb] - c >= 0 ? 0 : 1; //是否需要借位a[i + fa] = (10 + a[i + fa] - b[i + fb] - c) % 10;l = a[i + fa] ? i + fa : l; //判断末尾位置c = s;}if (l < 0)printf("0");elseshow(l);}int main() {scanf("%s%s", a, b);fa = ('-' == a[0]), fb = ('-' == b[0]);// 我们早两者如果只有一个负数的时候，我们让前一个数大的原因是这样我们就可以通过前一个确实整个的符号if ( !cmp())swap(a, b), swap(fa, fb);la = strlen(a), lb = strlen(b);reverse(a + fa, a + la), reverse(b + fb, b + lb); // 易忘int i = fa, j = fb;while (i < la)a[i] -= '0', i ++;while (j < lb)b[j] -= '0', j ++;//j容易写成iif (fa ^ fb)minu(); // 两个只有有一个有负号 ，减法elseadd(); // 加法return 0;}

大数减法

两个数都是整数，且相减结果大于0

// C = A - B, 满足A >= B, A >= 0, B >= 0vector<int> sub(vector<int> &A, vector<int> &B){    vector<int> C;    for (int i = 0, t = 0; i < A.size(); i ++ )    { t = A[i] - t; if (i < B.size()) t -= B[i]; C.push_back((t + 10) % 10); if (t < 0) t = 1; else t = 0;    }    while (C.size() > 1 && C.back() == 0) C.pop_back();    return C;}

两个数都是正整数，相减结果可以是负数

#include #include #include #include #include using namespace std;char a[1000005];char b[1000005];int la, lb;//比较大小int cmp() {int la = strlen(a), lb = strlen(b);if (la  > lb ) // 比较长度return 1;else if (la  < lb )return 0;else {// 长度相等则看每一位int i  = 0;while (i < la && a[i] == b[i])i ++;return a[i] >  b[i];}}void minu() {int i, j, t = 0, ed = -1;for (i = 0; i < la || i < lb; ++i) {int s = a[i] - b[i] - t >= 0 ? 0 : 1; //是否需要借位a[i] = (10 + a[i] - b[i] - t) % 10;ed = a[i] ? i  : ed; //判断末尾位置t = s;}if (ed < 0)printf("0");elsefor (int i = ed ; i >= 0 ; --i)printf("%d", a[i]);}int main() {scanf("%s%s", a, b);// 我们早两者如果只有一个负数的时候，我们让前一个数大的原因是这样我们就可以通过前一个确实整个的符号if ( !cmp()) {cout << '-';swap(a, b);}la = strlen(a), lb = strlen(b);reverse(a, a + la), reverse(b, b + lb);   // 易忘int i = 0, j = 0;while (i < la)a[i] -= '0', i ++;while (j < lb)b[j] -= '0', j ++;//j容易写成iminu();return 0;}

两个数均可以是负数

#include #include #include using namespace std;string a, b, s, t;int fa, fb;void init() {fa = (a[0] == '-'), fb = (b[0] == '-');s = a.substr( 1, a.size() ), t = b.substr( 1, b.size() );}bool cmp(string a, string b) {int as = a.size(), bs = b.size();if (as > bs || as == bs && a > b)return true;elsereturn false;}void change(string &s, string &t, string a, string b) {int as = a.size(), bs = b.size(), d = as > bs ? as - bs : bs - as;for ( int i = 0; i < d; i++ )as > bs ? t += "0" : s += "0";s += a, t += b; // 前边补上0}string calcAddition( string a, string b ) {string s = "0", t = "0";//多放的一个0是加法可能会进一位change(s, t, a, b);int len = s.size();for ( int i = len - 1; i >= 1; i-- )s[i] += t[i] - '0';if ( s[i] > '9' ) {s[i] -= 10;s[i - 1]++;}bool j = true;for ( int i = 0; i < len; i++ )if ( s[i] != '0' )j = false;if ( j )return "0";return s[0] == '0' ? s.substr( 1, len ) : s;}string calcSubtraction( string a, string b ) {string s = "", t = "";change(s, t, a, b);if ( s < t )swap(s, t);int len = s.size();for ( int i = len - 1; i >= 0; i-- ) {if ( s[i] < t[i] ) {s[i] += 10;if ( s[i - 1] >= '1' )s[i - 1]--;else { // 否则向前边不是0的借位int j = i - 1;while ( s[j] == '0' )s[j--] += 9;//s[j]--;}}s[i] -= ( t[i] - '0' );}if ( len == 1 )return s;return s[0] == '0' ? calcAddition( s.substr( 1, len ), "0" ) : s;}int main() {cin >> a >> b;init();if ( fa && fb ) {if ( cmp(s, t) )cout << "-";cout << calcSubtraction( s, t ) << endl;} else if ( !fa && !fb ) {if (!cmp(a, b) )cout << "-";cout << calcSubtraction( a, b ) << endl;} else if ( fa )cout << "-" << calcAddition( s, b ) << endl;elsecout << calcAddition( a, t ) << endl;return 0;}

高精度乘法

一个结论是：两个相乘的数，第一个数的第i为与第二个数的第j位（从1开始），相乘的结果是累加到第 结果的第i + j - 1位上的。

两个数均可以是负数

#include #include #define T 1000000using namespace std;char a1[T], b1[T];int a[T], b[T], c[T], lena, lenb, lenc, x, t, f;void mul() {for (int i = 1; i <= lena; i++) {x = 0;//x是进位for (int j = 1; j <= lenb; j++) {c[i + j - 1] += a[i] * b[j] + x ;x = c[i + j - 1] / 10;c[i + j - 1] %= 10;}c[i + lenb] = x;}lenc = lena + lenb;while (c[lenc] == 0 && lenc > 1)lenc--;if (f == -1)cout << "-";for (int i = lenc; i >= 1; i--)cout << c[i];cout << endl;}int main() {cin >> a1 >> b1 ;lena = strlen(a1), lenb = strlen(b1);f = 1, t = 0;if (a1[0] == '-')  //判断第一个字符是不是负数，如果是，再判断另一个是不是，再想输出问题对于B1字符数组同理f *= -1, t++;for (int i = t; i <= lena - 1; i++)a[lena - i] = a1[i] - '0'; //除去符号位后，将字符变成数字，放在对应的int数组里面，进行计算t = 0;if (b1[0] == '-')f *= -1, t++;for (int i = t; i <= lenb - 1; i++)b[lenb - i] = b1[i] - '0';mul();return 0;}

大数除法

两个数均可以是负数

#include #include using namespace std;string fixedNum( string a ) {if ( a.size() == 1 )return a;for ( int i = 0; i < a.size(); i++ )if ( '1' <= a[i] && a[i] <= '9' )return a.substr( i, a.size() );return "0";}string calcAddition( string a, string b ) {a = fixedNum(a);b = fixedNum(b);int as = a.size(), bs = b.size(), d = as > bs ? as - bs : bs - as;string s = "0", t = "0";for ( int i = 0; i < d; i++ )as > bs ? t += "0" : s += "0";s += a;t += b;for ( int i = s.size() - 1; i >= 1; i-- ) {s[i] += t[i] - '0';if ( s[i] > '9' ) {s[i] -= 10;s[i - 1]++;}}return s[0] == '0' ? s.substr( 1, s.size() ) : s;}string calcSubtraction( string a, string b ) {int as = a.size(), bs = b.size(), d = as - bs;string s = "", t = "";for ( int i = 0; i < d; i++ )t += "0";s += a;t += b;for ( int i = s.size() - 1; i >= 0; i-- ) {if ( s[i] < t[i] ) {s[i] += 10;if ( s[i - 1] >= '1' )s[i - 1]--;else {int j = i - 1;while ( s[j] == '0' )s[j--] += 9;s[j]--;}}s[i] -= ( t[i] - '0' );}if ( s.size() == 1 )return s;for ( int i = 0; i < s.size(); i++ ) {if ( '1' <= s[i] && s[i] <= '9' )return s.substr( i, s.size() );}return "0";}int main() {string a, b, c, sum = "0", cnt = "1";bool j1 = false;cin >> a >> b;if ( a == "0" ) {cout << 0 << endl;return 0;} else if ( a[0] == '-' && b[0] == '-' ) {a = a.substr( 1, a.size() );b = b.substr( 1, b.size() );} else if ( a[0] == '-' ) {j1 = true;a = a.substr( 1, a.size() );} else if ( b[0] == '-' ) {j1 = true;b = b.substr( 1, b.size() );} else;c = b;int as = a.size(), bs = b.size(), cs, d = as - bs;for ( int i = 0; i < d - 1; i++ ) {c += "0";cnt += "0";}cs = c.size();bool j2 = false;while ( c != b ) {while ( as > cs || as == cs && a >= c ) {j2 = true;a = calcSubtraction( a, c );as = a.size();sum = calcAddition( sum, cnt );}c = c.substr( 0, c.size() - 1 );cnt = cnt.substr( 0, cnt.size() - 1 );cs = c.size();}while ( as > bs || as == bs && a >= b ) {j2 = true;a = calcSubtraction( a, b );sum = calcAddition( sum, cnt );as = a.size();}if ( j1 && j2 )cout << '-';cout << sum << endl;return 0;}

大数取模

#include #include using namespace std;string calcAddition( string a, string b ) {int as = a.size(), bs = b.size(), d = as > bs ? as - bs : bs - as;string s = "0", t = "0";for ( int i = 0; i < d; i++ )as > bs ? t += "0" : s += "0";s += a;t += b;for ( int i = s.size() - 1; i >= 1; i-- ) {s[i] += t[i] - '0';if ( s[i] > '9' ) {s[i] -= 10;s[i - 1]++;}}bool j = true;for ( int i = 0; i < s.size(); i++ )if ( s[i] != '0' )j = false;if ( j )return "0";return s[0] == '0' ? s.substr( 1, s.size() ) : s;}string calcSubtraction( string a, string b ) {int as = a.size(), bs = b.size(), d = as - bs;string s = "", t = "";for ( int i = 0; i < d; i++ )t += "0";s += a;t += b;for ( int i = s.size() - 1; i >= 0; i-- ) {if ( s[i] < t[i] ) {s[i] += 10;if ( s[i - 1] >= '1' )s[i - 1]--;else {int j = i - 1;while ( s[j] == '0' )s[j--] += 9;s[j]--;}}s[i] -= ( t[i] - '0' );}if ( s.size() == 1 )return s;for ( int i = 0; i < s.size(); i++ ) {if ( '1' <= s[i] && s[i] <= '9' )return s.substr( i, s.size() );}return "0";}int main() {string a, b, c;cin >> a >> b;c = b;int as = a.size(), bs = b.size(), cs, d = as - bs;for ( int i = 0; i < d - 1; i++ )c += "0";cs = c.size();while ( c != b ) {while ( as > cs || as == cs && a >= c ) {a = calcSubtraction( a, c );as = a.size();}c = c.substr( 0, c.size() - 1 );cs = c.size();}while ( as > bs || as == bs && a >= b ) {a = calcSubtraction( a, b );as = a.size();}cout << a << endl;return 0;}