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;
}