[7. high precision division]

High precision division

Ideas ：

• High precision integers divided by low precision integers , Shang Wei C, Remainder is r.
• Divide the high order by the low precision integer . Quotient exists in the array ,r * 10 + The latter , Continue to divide by low precision integers . Until the cycle ends .
• Remove the lead 0

step :

1. In order to add with high precision 、 Subtraction 、 The multiplication template is consistent , Here, reverse order storage is also used , The only difference is , Here is the operation from the high order , Before that, the operation was carried out from the low order
2. Set remainder , Initial value by 0, High precision integers are divided by low precision integers from high order , Quotient exists in the array , remainder r * 10 + The latter , Continue with the calculation .
3. Flip （ Previous high-precision integers 123 + 10, Stored in the array in reverse order , Operate from the low order 321 + 01. Multiplication, on the other hand, requires high-order operations , So you need to turn it over ）
4. Remove the lead 0
5. Print in reverse order

give an example

Code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// A / b, Business is C,  The remainder is r
vector<int> div(vector<int> &A, int b , int &r) //r  Is quoted 
{
     
   vector<int> C;
   r = 0;         
   for (int i = A.size() - 1; i >= 0; i --)
   {
     
       r = r * 10 + A[i];
       C.push_back(r / b);
       r %= b;
   }
   
   reverse(C.begin(), C.end());                         // Flip array elements 
   while (C.size() > 1 && C.back() ==0) C.pop_back();   // Remove the lead 0
   return C;
}

int main()
{
     
   string a;
   int b;
   
   cin >> a >> b;
   
   vector<int> A;
   for (int i = a.size() - 1; i >= 0; i --) A.push_back(a[i] - '0');
   
   int r;       // remainder 
   auto C = div(A, b ,r);
   
   for (int i = C.size() - 1; i >= 0; i --) printf("%d",   C[i]);
   cout << endl << r <<endl;
}