CFR 198 1A. About Bacteria ( Math )

Problem - A - Codeforces
f( x ) = k * x + b
f^n( 1 ) ≤ f^a( t ) となるような最小な aを求める。
始めは matrix fast power で二分探査しようと頑張ってみたがオーバーフローが出るみたいで失敗した。
ちゃんと考えると、単調増加関数なので両方に f^( -a )() をかけたら、条件が f^( n - a ) ≤ t になる。それなら簡単だね。

#include <bits/stdc++.h>
using namespace std;
const int MAXV = 1e6 + 6;
typedef long long ll;

int k, b, n, t;

int main(){
    scanf("%d%d%d%d", &k, &b, &n, &t);
    ll cur = 1; int cnt = 0;
    while( cur <= t )
        cur = cur * k + b,
        ++cnt;
    printf("%d\n", max( 0, n - cnt + 1 ));
    return 0;
}