高精度

用高精度处理很长很长的数字。

基本思想是压位, 压n位即用数组一个元素表示n位数(从右往左读)。(可以理解为10^n进制)

注意如果用结构体+vector来存储，操作前先将vector::clear()，因为会执行合成的构造函数。

如果压1位，则一般从a[1]开始存，a[0]表示长度。很好用。

用字符串来读取数据再用结构体或直接用普通数组来存储。

四则运算则一般通过模拟竖式解决。

进位可以当成10^n进制来想。

但高精度除以高精度(高精度mod高精度)有点例外，下面再讲。

压n位存储

从右往左，每次截取n位。保险起见用long long来存

存储整型

从右往左，每一位读取num % 10^n，然后num /= 10^n。

存储字符串

算范围:

  • start=str.length - i * WIDTH;
  • end=max(0,end - WIDTH);

相关api：

  • sscanf(cstring,”%ll”,&x): 将cstring存储到整型变量x中
  • string::substr(start, end): 截取范围[start, end]的字符串。

输出

相关api

  • ssprintf(cstrinig,”%08d”,x): 以宽度为8把整型n存到cstring中，向右对齐补0.

注意

  • 首位可能不足n位，所以一般先将首位输出，再输出其余位。
  • 前导零。
  • 输出零。(-0)

高精度 / 高精度

一般思路是通过减法实现，求被除数减去除数能够减多少次。

有一种更高效的方法：

补“0”法(来自: 洛谷yejichen)

此法不同于一般的模拟（竖式法），除法操作步数模仿手工除法，而是利用减法操作实现的。

其基本思想是反复做除法，看从被除数里面最多能减去多少个除数，商就是多少。

逐个减显然太慢，要判断一次最多能减少多少个整的10的n次方。

以7546除23为例。

先减去23的100倍，就是2300，可以减3次，余下646。此时商就是300；

然后646减去23的10倍，就是230，可以减2次，余下186。此时商就是320；

然后186减去23，可以减8次，此时商就是328。

从这里不难看出，所谓补“0”只不过是减得快一点罢了，其本质依旧是高精度乘法的逆运算。

(不过我自己实现的时候由于memset和数组传递的原因，在数组迭代更新的地方有点乱，稍微改一改就好了，思路是这样。用vector因该比较方便。)

看到过二分找商，用乘法来验算，很简单了。

板子

压8位(基本输入输出 关系比较 加减法 高精度乘法 高精度除以低精)

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll; 
  4. struct BigInteger
  5. {
  6.     friend BigInteger operator+(const BigInteger &lhs,const BigInteger &rhs);
  7.     static const int BASE = 100000000;
  8.     static const int WIDTH = 8;
  9.     vector<ll> s;
  10.     BigInteger(ll num = 0){*this = num;}
  11.     BigInteger operator = (ll num)
  12.     {
  13.         s.clear();
  14.         do
  15.         {
  16.             s.push_back(num % BASE);
  17.             num /= BASE;
  18.         }while(num > 0);
  19.         return *this;
  20.     }
  21.     // 从右往左压位存
  22.     BigInteger operator = (const string& str)
  23.     {
  24.         s.clear();
  25.         int x,len = (str.length() - 1) / WIDTH + 1;// 注意数组从0开始数 
  26.         for(int i = 0;i < len;i ++)
  27.         {
  28.             // 从后截取一段长度为WIDTH的字符 
  29.             int end = str.length() - i * WIDTH;
  30.             int start = max(0, end - WIDTH);
  31.             sscanf(str.substr(start, end-start).c_str(),"%d",&x);
  32.             s.push_back(x);
  33.         }
  34.         return *this;
  35.     }
  36.     BigInteger operator += (const BigInteger& rhs)
  37.     {
  38.         *this = *this + rhs;
  39.         return *this;
  40.     }
  41. };
  43. BigInteger operator+(const BigInteger &lhs,const BigInteger &rhs)
  44. {
  45.     BigInteger sum;
  46.     sum.s.clear();// 重要 重置初始化 
  47.     for(int i = 0,g = 0;;i ++)// g是上次加法所进位 
  48.     {
  49.         if(g == 0 && i >= lhs.s.size() && i >= rhs.s.size()) break;
  50.         ll x = g;
  51.         if(i < lhs.s.size()) x += lhs.s[i];
  52.         if(i < rhs.s.size()) x += rhs.s[i];
  53.         sum.s.push_back(x % BigInteger::BASE);
  54.         g = x / BigInteger::BASE;
  55.     }
  56.     return sum;
  57. }
  60. bool operator<(const BigInteger &lhs,const BigInteger &rhs)
  61. {
  62.     if(lhs.s.size() != rhs.s.size()) return lhs.s.size() < rhs.s.size();
  63.     for(int i = lhs.s.size() - 1;i >= 0;i --)
  64.         if(lhs.s[i] != rhs.s[i]) return lhs.s[i] < rhs.s[i];
  65.     return 0;// 相等0 
  66. }
  68. // 返回两数相减的绝对值 
  69. BigInteger operator-(const BigInteger &lhs,const BigInteger &rhs) 
  70. {
  71.     BigInteger l = lhs,r = rhs;
  72.     BigInteger dif;
  73.     dif.s.clear();// 重要 重置初始化 
  74.     if(l < r) 
  75.         swap(l,r);// 保证左值最大
  76.     for(int i = 0;i < l.s.size();i ++)
  77.     {
  78.         ll x = l.s[i];
  79.         if(i < r.s.size()) 
  80.             x -= r.s[i];// 注意越界 
  81.         if(x < 0)// 借位 
  82.         {
  83.             x += BigInteger::BASE;
  84.             l.s[i + 1] --;
  85.         } 
  86.         dif.s.push_back(x);
  87.     }
  88.     return dif;
  89. }
  92. bool operator>(const BigInteger &lhs,const BigInteger &rhs)
  93. {
  94.     return rhs < lhs;
  95. }
  97. bool operator<=(const BigInteger &lhs,const BigInteger &rhs)
  98. {
  99.     return !(rhs < lhs);
  100. }
  102. bool operator>=(const BigInteger &lhs,const BigInteger &rhs)
  103. {
  104.     return !(lhs < rhs);
  105. }
  107. bool operator==(const BigInteger &lhs, const BigInteger &rhs)
  108. {
  109.     return !(lhs < rhs) && !(rhs < lhs);
  110. }
  112. bool operator!=(const BigInteger &lhs,const BigInteger &rhs)
  113. {
  114.     return !(lhs == rhs);
  115. }
  117. ostream &operator<<(ostream &os, const BigInteger &x)
  118. {
  119.     os << x.s.back();// 首位可能长度不足WIDTH 
  120.     for(int i = x.s.size() - 2;i >= 0;i --)
  121.     {
  122.         char buf[20];
  123.         sprintf(buf, "%08d" ,x.s[i]);// x.s[i]可能为ll(00012345) 补前面的0 
  124.         for(int j = 0;j < strlen(buf); j++) os << buf[j];
  125.     }
  126.     return os;
  127. }
  129. istream &operator>>(istream &is, BigInteger &x)
  130. {
  131.     string s;
  132.     if(!(is >> s)) return is;
  133.     x = s;
  134.     return is;
  135. }
  137. int main()
  138. {
  139.     string a,b;cin >> a >> b;
  140.     BigInteger x,y;
  141.     x = a;
  142.     y = b;
  143.     if(a == b) cout << 0;
  144.     else{
  145.         if(x < y) cout << "-";
  146.         cout << operator-(x,y);
  147.     }
  148.     return 0;
  149. }

压1位(所有四则运算和取余)

高精度四则运算

  1. #include <bits/stdc++.h>
  2. #define MAXN 60000
  3. using namespace std;
  4. typedef long long ll;
  6. void value(string x,ll (&a)[MAXN])
  7. {
  8.     memset(a,0,sizeof(a)); 
  9.     a[0] = x.size();
  10.     for(int i = 1;i <= a[0];i ++)
  11.         a[i] = x[a[0] - i] - '0';
  12. }
  14. void print(const ll (&a)[MAXN])
  15. {
  16.     bool ok = 0;
  17.     for(int i = a[0];i >= 1;i --)
  18.     {
  19.         if(a[i] != 0) ok = 1;
  20.         if(ok) putchar(a[i] + '0');
  21.     }
  22.     if(!ok) putchar('0');
  23.     putchar('\n');
  24. }
  26. void add(const ll (&a)[MAXN],const ll (&b)[MAXN],ll (&c)[MAXN])
  27. {
  28.     memset(c,0,sizeof(c));
  29.     for(int i = 1,g = 0;;i ++)
  30.     {
  31.         if(g == 0 && i > a[0] && i > b[0]) break;
  32.         c[i] = (g + a[i] + b[i]) % 10;
  33.         g = (g + a[i] + b[i]) / 10;
  34.     }
  35.     c[0] = max(a[0],b[0]);
  36.     if(c[c[0] + 1]) c[0] ++;
  37. }
  39. void multi(const ll (&a)[MAXN],const  ll(&b)[MAXN], ll(&c)[MAXN])
  40. {
  41.     memset(c,0,sizeof(c));
  42.     for(int i = 1;i <= b[0];i++)
  43.     {
  44.         for(int j = 1;j <= a[0]; j++)
  45.         {
  46.             int k = i + j - 1;
  47.             c[k] += b[i] * a[j];
  48.         }
  49.     }
  50.     c[0] = a[0] + b[0];
  51.     for(int i = 1;i <= c[0];i ++)
  52.         if(c[i] > 9)
  53.         {
  54.             c[i + 1] += c[i] / 10;
  55.             c[i] %= 10;
  56.         }
  57.     while(c[c[0]] == 0 && c[0] > 1)// 保证有1位(0) 
  58.         c[0]--;
  59. } 
  61. bool bigger(ll (&a)[MAXN], ll (&b)[MAXN])
  62. {
  63.     if(a[0] != b[0]) return a[0] > b[0];
  64.     for(int i = a[0];i >= 1;i --)
  65.         if(a[i] != b[i]) return a[i] > b[i];
  66.     return 0;// 相等 
  67. }
  69. bool minu(ll (&a)[MAXN], ll(&b)[MAXN], ll(&c)[MAXN])// c=a-b绝对值 返回是否为负数 
  70. {
  71.     bool big = bigger(b,a);
  72.     memset(c,0,sizeof(c));
  73.     if(big) swap(a,b);
  74.     for(int i = 1;i <= a[0];i ++)
  75.     {
  76.         c[i] += a[i] - b[i];
  77.         if(c[i] < 0)
  78.         {
  79.             c[i] += 10;
  80.             c[i + 1]--;
  81.         }
  82.     }
  83.     c[0] = max(a[0], b[0]);
  84.     while(c[c[0]] == 0 && c[0] > 1) c[0]--; 
  85.     return big;
  86. }
  88. // 方便memset和传递 
  89. void div(ll (&a)[MAXN], ll(&b)[MAXN], ll(&c)[MAXN], ll(&moveb)[MAXN], ll(&temp)[MAXN])
  90. {
  91.     memset(c,0,sizeof(c));
  92.     // 处理两种特殊情况: 相等和小于 
  93.     if(bigger(b,a))
  94.     {
  95.         c[0] = 1;
  96.         c[1] = 0;
  97.         return;
  98.     }
  99.     if(!bigger(a,b) && !bigger(b,a))
  100.     {
  101.         c[0] = 1;
  102.         c[1] = 1;
  103.         return;
  104.     }
  105.     ll t = a[0] - b[0];
  106.     c[0] = max(a[0],b[0]);
  107.     while(t >= 0)
  108.     {
  109.         memset(moveb,0,sizeof(moveb));
  110.         // 移动 
  111.         moveb[0] = t + b[0];
  112.         for(int i = 1;i <= b[0];i ++)
  113.             moveb[t + i] = b[i];
  114.         for(int i = 0;i <= a[0];i ++) temp[i] = a[i];
  115.         while(bigger(temp,moveb))
  116.         {
  117.             minu(a,moveb,temp);
  118.             c[t + 1] ++;
  119.             for(int i = 0;i <= temp[0];i ++) a[i] = temp[i];
  120.         }
  121.         t --;
  122.     }
  123.     while(c[c[0]] == 0 && c[0] > 1) c[0]--;
  124. }
  126. void mod(ll (&a)[MAXN], ll(&b)[MAXN], ll(&c)[MAXN], ll(&moveb)[MAXN])
  127. {
  128.     memset(c,0,sizeof(c));
  129.     // 处理两种特殊情况: 相等和小于 
  130.     if(bigger(b,a))
  131.     {
  132.         for(int i = 0;i <= a[0];i ++) c[i] = a[i];
  133.         return;
  134.     }
  135.     if(!bigger(a,b) && !bigger(b,a))
  136.     {
  137.         c[0] = 0;
  138.         c[1] = 0;
  139.         return;
  140.     }
  141.     ll t = a[0] - b[0];
  142.     c[0] = max(a[0],b[0]);
  143.     while(t >= 0)
  144.     {
  145.         memset(moveb,0,sizeof(moveb));
  146.         // 移动 
  147.         moveb[0] = t + b[0];
  148.         for(int i = 1;i <= b[0];i ++)
  149.             moveb[t + i] = b[i];
  150.         for(int i = 0;i <= a[0];i ++) c[i] = a[i];
  151.         while(bigger(c,moveb))
  152.         {
  153.             minu(a,moveb,c);
  154.             for(int i = 0;i <= c[0];i ++) a[i] = c[i];
  155.         }
  156.         t --;
  157.     }
  158.     while(c[c[0]] == 0 && c[0] > 1) c[0]--;
  159. } 
  161. ll a[MAXN],b[MAXN],c[MAXN], moveb[MAXN],temp[MAXN]; 
  162. int main()
  163. {
  164.     string x,y;cin >> x >> y;
  165.     value(x,a);
  166.     value(y,b);
  167.     add(a,b,c);
  168.     print(c);
  169.     value(x,a);
  170.     value(y,b);
  171.     if(minu(a,b,c)) putchar('-');
  172.     print(c);
  173.     value(x,a);
  174.     value(y,b);
  175.     multi(a,b,c);
  176.     print(c);
  177.     value(x,a);
  178.     value(y,b);
  179.     div(a,b,c,moveb,temp);
  180.     print(c);
  181.     value(x,a);
  182.     value(y,b);
  183.     mod(a,b,c,moveb);
  184.     print(c);
  185.     return 0;
  186. }

高精度除以低精度

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int main()
  4. {
  5.     string a;long long b,d = 0;vector<int> ans; 
  6.     cin >> a >> b;
  7.     // 从左往右存
  8.     for(int i = 0;i < a.length();i ++)
  9.     {
  10.         int t = a[i] - '0';
  11.         ans.push_back((d * 10 + t) / b);
  12.         d = (d * 10 + t) % b;
  13.     }
  14.     bool ok = false;
  15.     for(int i = 0;i < ans.size();i ++)
  16.     {
  17.         if(ans[i] != 0) ok = true;// 前导零 
  18.         if(ok) cout << ans[i];
  19.     }
  20.     return 0;
  21. }