Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cmath>
- using namespace std;
- typedef unsigned long long llg;
- llg sum(llg n, llg a1, llg b) {
- return (a1*(powl(b, n)-1))/(b-1);
- }
- llg search(llg& n, llg& a1, llg& b, llg& max) {
- llg left = 0;
- llg right = n;
- llg middle;
- while(true) {
- middle = left+(right-left)/2;
- llg value = sum(middle, a1, b);
- if(right-left == 1) {
- if(max > value) return left;
- else return sum(left-1, a1, b);
- }
- if(value > max) {
- right = middle;
- } else if(value < max) {
- left = middle;
- } else return middle;
- }
- }
- int main() {
- llg n, a1, b, max;
- cin >> n >> a1 >> b >> max;
- if(n == 1 || max == a1) {
- cout << 1 << endl;
- return 0;
- }
- if(b == 1) {
- cout << (max/a1) << endl;
- return 0;
- }
- if(max < a1) {
- cout << 0 << endl;
- return 0;
- }
- cout << search(n, a1, b, max) << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement