高精度计算(Arbitrary-Precision Arithmetic),也被称作大整数(bignum)计算,运用了一些算法结构来支持更大整数间的运算(数字大小超过语言内建整型)。
先决条件
快读
C++重载运算符
高精度算法
求 A 、 B A、B A 、 B 的和差积商余!
题目描述
两个数两行
A B A \ B A B
输入格式
五个数
和 差 积 商 余
输出格式
输入输出样例
输入
输出
说明/提示
l e n g ( A ) , l e n g ( B ) < = 1 0 4 leng(A),leng(B)<=10^4 l e n g ( A ) , l e n g ( B ) < = 1 0 4
A , B > 0 A,B>0 A , B > 0 每个点 3 s 3s 3 s 。
解决方案
原理
用数组模拟高精度类型,如1024
可以表示成:
1 2 3 4 5 6 7 8 9 索引: +---+---+---+---+---+ | 0 | 1 | 2 | 3 | 4 | +---+---+---+---+---+ 内容: +---+---+---+---+---+ | 4 | 4 | 2 | 0 | 1 | +---+---+---+---+---+
可知数组第 0 0 0 位存的是该大整数的位数,然后从个位依次往后存储每一位数字。
声明
由此可声明大整数类bigint
如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class bigint { private : bool minus; int num[maxn]; public : bigint(); bigint(const int &n); operator int () const ; void read () ; void print () const ; bool operator <(const bigint &x) const ; bool operator <=(const bigint &x) const ; bool operator !=(const bigint &x) const ; bool operator ==(const bigint &x) const ; bool operator >(const bigint &x) const ; bool operator >=(const bigint &x) const ; bigint operator +(const bigint &x) const ; bigint operator -() const ; bigint operator -(const bigint &x) const ; bigint operator *(const bigint &x) const ; bigint operator /(const bigint &x) const ; bigint operator %(const bigint &x) const ; bigint operator =(const int &x); bigint abs () const ; };
输入输出
先是bigint
类型的初始化和输入输出:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 bigint::bigint() { minus = false ; memset (num, 0 , sizeof (num)); num[0 ] = 1 ; } void bigint::read () { memset (num, 0 , sizeof (num)); char s[maxn]; scanf ("%1s" , s + 1 ); if (s[1 ] == '-' ) { minus = true ; scanf ("%s" , s + 1 ); } else { scanf ("%s" , s + 2 ); } num[0 ] = strlen (s + 1 ); for (int i = 1 ; i <= num[0 ]; i++) { num[i] = s[num[0 ] - i + 1 ] - '0' ; } } void bigint::print () { if (minus) printf ("-" ); for (int i = num[0 ]; i >= 1 ; i--) { printf ("%d" , num[i]); } }
比较运算
由于高精度减法需要用到大整数的比较运算,不妨先写一下比较运算。比较运算看似有<
, <=
, !=
, ==
, >
, >=
这六类,但实际上只需要写<
和==
就可以了,原因如下:
类型
条件
<=
<
或==
>
<
的反向
>=
>
或==
!=
<
且>
因此只需要写好<
和==
的重载,其他比较运算符只需要调用已有接口即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 bool bigint::operator <(const bigint &b) const { if (minus != b.minus) return minus > b.minus; if (num[0 ] != b.num[0 ]) return num[0 ] < b.num[0 ]; for (int i = num[0 ]; i >= 1 ; i--) { if (num[i] != b.num[i]) return num[i] <= b.num[i]; } return false ; } bool bigint::operator <=(const bigint &b) const { if (*this < b || *this == b) return true ; else return false ; } bool bigint::operator !=(const bigint &b) const { if (*this < b || b < *this ) return true ; else return false ; } bool bigint::operator ==(const bigint &b) const { if (minus != b.minus) return false ; if (num[0 ] != b.num[0 ]) return false ; for (int i = num[0 ]; i >= 1 ; i--) { if (num[i] != b.num[i]) return false ; } return true ; } bool bigint::operator >=(const bigint &b) const { if (b < *this || b == *this ) return true ; else return false ; } bool bigint::operator >(const bigint &b) const { if (b < *this ) return true ; else return false ; }
取绝对值、取相反数与强制类型转换
再顺便写一下取相反数,绝对值和int
与bigint
的互相转化。这里重载了int
强制类型转换,同时对于int
向bigint
的转换,采取的 Modern C++所倡导的形如bigint(x)
样式的显式转换,而非(bigint)x
样式的传统 C 语言强制类型转换,以保证安全性。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 bigint::bigint(const int &n) { int tmp = n; minus = tmp < 0 ; memset (num, 0 , sizeof (num)); while (tmp > 0 ) { num[++num[0 ]] = tmp % 10 ; tmp /= 10 ; } if (num[0 ] == 0 ) num[0 ] = 1 ; } bigint::operator int () const { int n = 0 ; for (int i = num[0 ]; i >= 1 ; i--) { n *= 10 ; n += num[i]; } return n; } bigint bigint::operator -() const { bigint c = *this ; c.minus ^= 1 ; return c; } bigint bigint::abs () const { bigint c = *this ; if (c < bigint(0 )) c = (-c); return c; }
四则运算
至此正式写高精前的准备工作就完成了。
事实上高精度算法的本质是模拟人工列竖式计算的过程。如加法的做法是输入的两个数,按位相加,然后模拟进位即可。
然而不论加减乘除,我们都希望把复杂的情况转化为几种基本情况,比如加法中我们总是希望两个正数相加,减法中总是两个正数相减,且结果为正。
加法
对于加法来说,有这些情况:
a < 0 , b > 0 a < 0, \ b > 0 a < 0 , b > 0 ,则 a + b = b − ( − a ) ) a + b = b - (-a)) a + b = b − ( − a ) )
a < 0 , b < 0 a < 0, \ b < 0 a < 0 , b < 0 ,则 a + b = − ( ( − a ) + ( − b ) ) a + b = - ( (-a) + (-b) ) a + b = − ( ( − a ) + ( − b ) )
a > 0 , b > 0 a > 0, \ b > 0 a > 0 , b > 0 ,则 a + b = a + b a + b = a + b a + b = a + b
a > 0 , b < 0 a > 0, \ b < 0 a > 0 , b < 0 ,则 a + b = a − ( − b ) a + b = a - (-b) a + b = a − ( − b )
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 bigint bigint::operator +(const bigint &x) const { if ((*this ) == bigint(0 )) return x; if (x == bigint(0 )) return *this ; if (*this < bigint(0 ) && x > bigint(0 )) return x - (*this ).abs (); if (*this < bigint(0 ) && x < bigint(0 )) return -((*this ).abs () + x.abs ()); if (*this > bigint(0 ) && x < bigint(0 )) return (*this ) - x.abs (); bigint a = *this , b = x, c; c.num[0 ] = max(a.num[0 ], b.num[0 ]); for (int i = 1 ; i <= c.num[0 ]; i++) { c.num[i] += a.num[i] + b.num[i]; c.num[i + 1 ] += c.num[i] / 10 ; c.num[i] %= 10 ; } if (c.num[c.num[0 ] + 1 ]) c.num[0 ]++; return c; }
减法
减法稍微复杂一点,我们应该尽量将其转换成两个正数的加减法操作,可以分几种情况判断:
a < 0 , b > 0 a < 0, \ b > 0 a < 0 , b > 0 ,则 a − b = − ( ( − a ) + b ) a - b = - ((-a) + b) a − b = − ( ( − a ) + b )
a < 0 , b < 0 a < 0, \ b < 0 a < 0 , b < 0 ,则 a − b = ( − b ) − ( − a ) a - b = (-b) - (-a) a − b = ( − b ) − ( − a )
a > 0 , b > 0 a > 0, \ b > 0 a > 0 , b > 0 ,则 a − b = a − b a - b = a - b a − b = a − b
a > 0 , b < 0 a > 0, \ b < 0 a > 0 , b < 0 ,则 a − b = a + ( − b ) a - b = a + (-b) a − b = a + ( − b )
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 bigint bigint::operator -(const bigint &x) const { bigint a = *this , b = x, c; if (a == bigint(0 )) return -b; if (b == bigint(0 )) return a; if (a < bigint(0 ) && b > bigint(0 )) return -(-a + b); if (a < bigint(0 ) && b < bigint(0 )) return (-b) - (-a); if (a > bigint(0 ) && b < bigint(0 )) return a + (-b); if (a < b) { c.minus ^= 1 ; swap(a, b); } c.num[0 ] = a.num[0 ]; for (int i = 1 ; i <= c.num[0 ]; i++) { c.num[i] = a.num[i] - b.num[i]; } for (int i = 1 ; i <= c.num[0 ]; i++) { if (c.num[i] < 0 ) { c.num[i + 1 ] -= 1 ; c.num[i] += 10 ; } } while (!c.num[c.num[0 ]]) { if (c.num[0 ] == 1 ) break ; c.num[0 ]--; } return c; }
乘法
乘法需要注意的是,对于数 a , b a, \ b a , b , a a a 的第 i i i 位与 b b b 的第 j j j 之积对结果的第 i + j − 1 i + j - 1 i + j − 1 位有贡献,计算过程中注意实时向第 i + j i + j i + j 位进位。正负号方面, 符号不同为负,相同为正。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 bigint bigint::operator *(const bigint &x) const { bigint a = *this , b = x, c; if (a.abs () < b.abs ()) swap(a, b); c.minus = a.minus ^ b.minus; c.num[0 ] = a.num[0 ] + b.num[0 ]; for (int j = 1 ; j <= b.num[0 ]; j++) { for (int i = 1 ; i <= a.num[0 ]; i++) { c.num[i + j - 1 ] += a.num[i] * b.num[j]; c.num[i + j] += c.num[i + j - 1 ] / 10 ; c.num[i + j - 1 ] %= 10 ; } } while (!c.num[c.num[0 ]]) { if (c.num[0 ] == 1 ) { c = bigint(0 ); break ; } c.num[0 ]--; } return c; }
除法
除法同样是模拟竖式,不同的是,这里不纠结于商究竟是几位数字,而直接从最高位开始试除。高精度除法需要依赖高精度加、减、乘法。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 bigint bigint::operator /(const bigint &x) const { bigint a = *this , b = x, c, tmp, cnt; bool flag = a.minus ^ b.minus; a = a.abs (); b = b.abs (); tmp.num[0 ] = a.num[0 ]; tmp.num[tmp.num[0 ]] = 1 ; while (a > b) { cnt = bigint(0 ); while (b * tmp * (cnt + bigint(1 )) <= a) cnt = cnt + bigint(1 ); c = c + tmp * cnt; a = a - b * tmp * cnt; tmp.num[tmp.num[0 ]] = 0 ; tmp.num[0 ]--; tmp.num[tmp.num[0 ]] = 1 ; } if (!(c.num[0 ] == 1 && c.num[1 ] == 0 )) c.minus = flag; return c; }
取模
取模计算也很简单, b b b 对 a a a 取模的结果就是 a − ⌊ a / b ⌋ ∗ b a - \lfloor a / b \rfloor * b a − ⌊ a / b ⌋ ∗ b
1 2 3 4 5 bigint bigint::operator %(const bigint &x) const { bigint a = *this , b = x; return a - a / b * b; }
请参见