大整数运算

  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5. const int N = 1e6 + 10;
  7. // 加法
  8. vector<int> add(vector<int> &A,vector<int> &B){
  9.     vector<int>C;
  10.     int k = 0;
  11.     for(int i = 0; i < A.size() || i < B.size(); i ++){
  12.         if(i < A.size()) k += A[i];
  13.         if(i < B.size()) k += B[i];
  14.         C.push_back(k % 10);
  15.         k /= 10;
  16.     }
  17.     if(k) C.push_back(1);
  18.     return C;
  19. }
  21. //减法
  22. //判断A是否大于B
  23. bool cmp(vector<int> &A,vector<int> &B){
  24.     if(A.size() != B.size()) return A.size() > B.size();
  25.     else {
  26.         for(int i = A.size() - 1; i >= 0; i --){
  27.             if(A[i] != B[i]) return A[i] > B[i];
  28.         }
  29.     }
  30.     return true;
  31. }
  33. // 减法 (A >= B)
  34. vector<int> sub(vector<int> &A,vector<int> &B){
  35.     vector<int>C;
  36.     for(int i = 0,t = 0; i < A.size() ; i ++){
  37.         t = A[i] - t;
  38.         if(i < B.size()) t -= B[i];
  39.         C.push_back((t + 10) % 10);
  40.         if(t < 0) t = 1;
  41.         else t = 0;
  42.     }
  43.     while(C.size() > 1 && C.back() == 0) C.pop_back(); 
  44.     return C;
  45. }
  47. //乘法
  48. //高精度 * 低精度
  49. vector<int> mul(vector<int> &A, int b){
  50.     vector<int> C;
  51.     int t = 0;
  52.     for(int i = 0; i < A.size() || t; i ++){
  53.         if(i < A.size()) t += A[i] * b;
  54.         C.push_back(t % 10);
  55.         t /= 10;
  56.     }
  57.     return C;
  58. }
  60. //除法
  61. //高精度 / 低精度  商是C，余数是r
  62. vector<int> div(vector<int> &A, int b,int &r){
  63.     vector<int> C;
  64.     r = 0;
  65.     for(int i = A.size() - 1; i >= 0; i --){
  66.         r= r * 10 + A[i];
  67.         C.push_back(r / b);
  68.         r %= b;
  69.     }
  71.     reverse(C.begin(),C.end());
  73.     while(C.size() > 1 && C.back() == 0) C.pop_back();
  75.     return C;
  76. }
  79.  int main(){
  80.      string a;
  81.      int b;
  82.      cin >> a >> b;
  83.      vector<int> A;
  84.      for(int i = a.size() - 1; i >= 0; i --) A.push_back(a[i] - '0');
  85.      int r;
  86.      auto C = div(A, b,r);
  87.      for(int i = C.size() - 1; i >= 0; i --) printf("%d",C[i]);
  88.      cout << endl << r << endl;
  89.      return 0;
  90.  }