大数除以一个小数
1 #include <bits/stdc++.h> 2 using namespace std; 3 //A/b商是C，余数是r 4 vector<int> div(vector<int> &A, int b, int &r) { 5 vector<int> C; 6 r = 0; 7 //注意除法是从最高位开始算的 8 //前面那仨都是从最低位开始算 9 for (int i = A.size() - 1; i >= 0; i--) { 10 r = r * 10 + A[i]; 11 C.push_back(r / b); 12 r %= b; 13 } 14 //C[0]是最高位 15 reverse(C.begin(), C.end()); 16 while (C.size() > 1 && C.back() == 0) { 17 C.pop_back(); 18 } 19 return C; 20 } 21 int main () { 22 string a; 23 int b; 24 cin >> a >> b; 25 vector<int> A, C; 26 for (int i = a.length() - 1; i >= 0; i--) { 27 A.push_back(a[i] - '0'); 28 } 29 int r; 30 C = div(A, b, r); 31 for (int i = C.size() - 1; i >= 0; i--) { 32 cout << C[i]; 33 } 34 cout << endl << r << endl; 35 return 0; 36 }
2020年9月29日更新：压8位的做法
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int base = 1000000000; 5 vector<ll> div(vector<ll> &A, int b, ll &r) { 6 vector<ll> C; 7 r = 0; 8 for (ll i = A.size() - 1; i >= 0; i--) { 9 r = r * base + A[i]; 10 C.push_back(r / b); 11 r %= b; 12 } 13 reverse(C.begin(), C.end()); 14 while (C.size() > 1 && C.back() == 0) { 15 C.pop_back(); 16 } 17 return C; 18 } 19 int main() { 20 string a; 21 int b; 22 cin >> a >> b; 23 vector<ll> A, C; 24 for (ll i = a.size() - 1, s = 0, j = 0, t = 1; i >= 0; i--) { 25 s += (a[i] - '0') * t; 26 j++; 27 t *= 10; 28 if (j == 9 || i == 0) { 29 A.push_back(s); 30 s = 0; 31 j = 0; 32 t = 1; 33 } 34 } 35 36 ll r; 37 C = div(A, b, r); 38 cout << C.back(); 39 for (ll i = C.size() - 2; i >= 0; i--) { 40 cout << setw(9) << setfill('0') << C[i]; 41 } 42 cout << endl << r << endl; 43 return 0; 44 }