SHARE
TWEET

Untitled

a guest Oct 15th, 2019 73 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cmath>
  3. using namespace std;
  4.  
  5. typedef unsigned long long llg;
  6.  
  7. llg sum(llg n, llg a1, llg b) {
  8.     return (a1*(powl(b, n)-1))/(b-1);
  9. }
  10.  
  11. llg search(llg& n, llg& a1, llg& b, llg& max) {
  12.     llg left = 0;
  13.     llg right = n;
  14.     llg middle;
  15.     while(true) {
  16.         middle = left+(right-left)/2;
  17.         llg value = sum(middle, a1, b);
  18.         if(right-left == 1) {
  19.             if(max > value) return left;
  20.             else return sum(left-1, a1, b);
  21.         }
  22.         if(value > max) {
  23.             right = middle;
  24.         } else if(value < max) {
  25.             left = middle;
  26.         } else return middle;
  27.     }
  28. }
  29.  
  30. int main() {
  31.     llg n, a1, b, max;
  32.     cin >> n >> a1 >> b >> max;
  33.     if(n == 1 || max == a1) {
  34.         cout << 1 << endl;
  35.         return 0;
  36.     }
  37.     if(b == 1) {
  38.         cout << (max/a1) << endl;
  39.         return 0;
  40.     }
  41.     if(max < a1) {
  42.         cout << 0 << endl;
  43.         return 0;
  44.     }
  45.     cout << search(n, a1, b, max) << endl;
  46.     return 0;
  47. }
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