fork download
copy 
  1. #include <iostream>
  2.  
  3. namespace {
  4. unsigned numBits(unsigned val) {
  5.   // https://stackoverflow.com/a/8991271/4279
  6.   unsigned digits;
  7.   for (digits = 0; val > 0; val >>= 1)
  8.         digits++;
  9.   return digits;
  10. }
  11.  
  12. template<class bigint>
  13. bigint div(const bigint& lhs, const bigint& rhs) {
  14.     // https://stackoverflow.com/q/27801397/4279
  15.     bigint dividend = lhs;
  16.     bigint divisor = rhs;
  17.  
  18.     int k = numBits(dividend) + numBits(divisor);
  19.     bigint pow2 = 1;
  20.     pow2 <<= k + 1;
  21.  
  22.     bigint x = dividend - divisor;
  23.     bigint lastx = 0;
  24.     bigint lastlastx = 0;
  25.     while (1) {
  26.         x = (x * (pow2 - x * divisor)) >> k;
  27.         if (x == lastx || x == lastlastx) break;
  28.         lastlastx = lastx;
  29.         lastx = x;
  30.     }
  31.     bigint quotient = dividend * x >> k;
  32.     if (dividend - (quotient * divisor) >= divisor) quotient++;
  33.     return quotient;
  34. }
  35. }
  36. int main() {
  37. 	unsigned a, b;
  38.     return !((std::cin >> a >> b) && (std::cout << div(a, b)));
  39. }
Success #stdin #stdout 0s 4356KB
comments (?)
stdin
copy 
2 1
stdout
copy 
1
https://ideone.com/cGNsdl
language:
C++ (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!