高精度算法

所谓高精度算法，就是把一个大整数的每一位分开储存，分开操作，从而避免溢出。在某些时候，数据可能会大到long long类型都会溢出，这时候就需要用到高精度算法了。其实，高精度算法是比较鸡肋的，很少单独考察，而且通常会被模运算替代，使用次数越来越少。但不排除有些题目就是要用到高精度，比如NOIP2012 国王游戏，而且学习高精度算法可以加深对于加减乘除等基本运算的细节理解，也可以提升一下代码能力。

  1 #include <cstring>
  2 #include <iostream>
  3 #include <string>
  4 
  5 using namespace std;
  6 
  7 struct BigInteger {
  8     int num[maxn], len, flag; //flag用来表示是否为负数
  9 
 10     BigInteger(long long x = 0) {
 11         memset(num, 0, sizoef(num)); //切记要初始化！！！
 12         len = flag = 0;
 13         for (int i = 1; x; ++i)
 14             num[i] = x % 10, x /= 10, ++len;
 15     }
 16 
 17     BigInteger(string s = "0") {
 18         memset(num, 0, sizeof(num)); //切记要初始化!
 19         len = s.length(), flag = 0;
 20         for (int i = 1; i <= len; ++i)
 21             num[i] = s[len - i] - '0'; //不要忘记减去'0'
 22     }
 23 
 24     bool operator < (const BigInteger& rhs) const {
 25         if (len == rhs.len) { //小于运算符可将其他比较运算符表示出来
 26             for (int i = len; i >= 1; --i)
 27                 if (num[i] != rhs.num[i])
 28                     return num[i] < rhs.num[i];
 29             return false;
 30         }
 31         else return len < rhs.len;
 32     }
 33 
 34     void operator + (const BigInteger& rhs) {
 35         len = max(len, rhs.len);
 36         for (int i = 1; i <= len; ++i) {
 37             num[i] += rhs.num[i];
 38             if (num[i] > 9) { //加法进位
 39                 ++num[i + 1];
 40                 num[i] -= 10;
 41             }
 42         }
 43         if (num[len + 1]) ++len; //更新大整数的位数
 44     }
 45 
 46     void operator - (BigInteger& rhs) {
 47         if (*this < rhs)
 48             swap(*this, rhs), flag = 1; //保证被减数大于减数
 49         for (int i = 1; i <= len; ++i) {
 50             num[i] -= rhs.num[i];
 51             if (num[i] < 0) { //减法借位
 52                 --num[i + 1];
 53                 num[i] += 10;
 54             }
 55         }
 56         while (!num[len] && len > 1)
 57             --len; //更新位数,注意要加上len>1,否则为0时会出错
 58     }
 59 
 60     void operator * (const int& rhs) { //高精乘低精
 61         for (int i = 1; i <= len; ++i)
 62             num[i] *= rhs; //先每位乘上再处理进位
 63         for (int i = 1; i <= len; ++i)
 64             for (int j = i; num[j] > 9; ++j) {
 65                 num[j + 1] += num[j] / 10;
 66                 num[j] %= 10;
 67             }
 68         len += 15; //因为新增加的位数不超过15
 69         while (!num[len] && len > 1) --len;
 70     }
 71 
 72     void operator * (const BigInteger& rhs) { //高精乘高精
 73         BigInteger ans = BigInteger(0);
 74         for (int i = 1; i <= len; ++i) //列成竖式再观察,会有此规律
 75             for (int j = 1; j <= rhs.len; ++j) {
 76                 ans.num[i + j - 1] += num[i] * rhs.num[j];
 77                 if (ans.num[i + j - 1] > 9) {
 78                     ans.num[i + j] += ans.num[i + j - 1]/10;
 79                     ans.num[i + j - 1] %= 10;
 80                 }
 81             }
 82         ans.len = len + rhs.len;
 83         //一个a位数和一个b位数相乘,结果最多为a+b位数
 84         while (!ans.num[ans.len] && ans.len > 1) --ans.len;
 85         *this = ans;
 86     }
 87 
 88     void operator / (const int& rhs) { //高精除以低精
 89         for (int i = len; i >= 1; --i) {
 90             num[i - 1] += num[i] % rhs * 10;
 91             num[i] /= rhs;
 92         }
 93         num[0] /= 10; //num[0]保存余数
 94         while (!num[len] && len > 1) --len;
 95     }
 96 
 97     BigInteger operator / (BigInteger& rhs) { //高精除以高精
 98         BigInteger ans = BigInteger(0);
 99         //返回商,原来的BigInteger保存余数
100         while (!(*this < rhs)) { //连续的减法模拟除法
101             *this - rhs;
102             ans + BigInteger("1");
103         }
104         return ans;
105     }
106 
107     void print() {
108         if (flag) cout << "-";
109         for (int i = len; i >= 1;--i) cout << num[i];
110     }
111 };