Codeforces Round #125 (Div. 1) A : About Bacteria
問題概要
f(x)=k*x+b(1≦k, b<10^6)な関数がある。f^n(1)≦f^a(t) (n,t<10^6)なる最小のaを求める問題。
解法
fが狭義単調増加であることから、f^n(1)≦f^a(t)はf^(n-a)(1)≦tと同値。したがってf^(n-a)(1)≦tを満たす最大のn-aを求めればよい。ただしaは非負。
acceptされたコード
#include <iostream> #include <algorithm> using namespace std; typedef long long int64; int64 K, B, N, T; int64 func(int64 x) { return K * x + B; } void init() { cin >> K >> B >> N >> T; } int solve() { int64 cur = 1; int turn; for (turn = 0;cur <= T; ++turn) { cur = func(cur); } return max(0, (int)(N - turn) + 1); } int main() { init(); cout << solve() << endl; return 0; }