SHARE
TWEET

Untitled

a guest Oct 22nd, 2019 88 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. bool test(ll a, ll b) {
  3.     // return true if (true value) >= a/b
  4.     ll n = 0, m = 1;
  5.  
  6.     rep(i, N) {
  7.         if (n < m*A[i].fi) n = A[i].fi, m = 1;
  8.  
  9.         ll c = b*n+m*a, d = m*b;
  10.         ll g = gcd(c, d);
  11.         n = c/g;
  12.         m = d/g;
  13.  
  14.         if (n > m*A[i].se) return false;
  15.     }
  16.     return true;
  17. }
  18.  
  19. pair<ll, ll> stern_brocot(ll M, ll N) {
  20.     // M : max value
  21.     // N : max divisor
  22.     // if result is a/b, return as {a, b}
  23.     ll a = 0, b = 1; // l
  24.     ll c = 1, d = 0; // r
  25.     int l, r;
  26.     bool chg = true;
  27.  
  28.     while(chg) {
  29.         chg = false;
  30.  
  31.         // to left
  32.         l = 0, r = (N-d-1)/b+1;
  33.         while(l < r) {
  34.             int mid = (l+r+1)/2;
  35.             if (test(a*mid+c, b*mid+d)) {
  36.                 r = mid-1;
  37.             } else {
  38.                 l = mid;
  39.             }
  40.         }
  41.  
  42.         c += a*l;
  43.         d += b*l;
  44.         chg |= (l > 0);
  45.  
  46.         // to right
  47.         l = 0, r = (d?(N-b-1)/d+1:M);
  48.         while(l < r) {
  49.             int mid = (l+r+1)/2;
  50.             if (test(a+mid*c, b+mid*d)) {
  51.                 l = mid;
  52.             } else {
  53.                 r = mid-1;
  54.             }
  55.         }
  56.  
  57.         a += c*l;
  58.         b += d*l;
  59.         chg |= (l > 0);
  60.     }
  61.  
  62.     return {a, b};
  63. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top