Codeforces Round #140 (Div. 1) C : Anniversary

問題概要

フィボナッチ数列の第L~R項までの中から異なるK個を選んでGCDをとる。GCDのとりうる最大値を求める問題。0

解法

まず、gcd(F[i],F[j])=F[gcd(i,j)]が成り立つ。したがって、[L,R]内に倍数をK個以上含むような最大のTについてF[T]が答となる。
[L,R]内にTの倍数は[R/T] - [(L-1)/T]個あるけど、興味があるのはTの最大値なので[R/T]の値が切り替わるようなところだけ調べれば良い。切り替わるところはO(sqrt(R))個しかないので間に合う。二分探索はダメ。

acceptされたコード

int64 L, R, K;

bool check(int64 x) {
	return R / x - (L - 1) / x >= K;
}

int solve() {
	int64 id = 0;
	for (int64 i = 1; i * i <= R; ++i) {
		if (check(i)) {
			updateMax<int64>(id, i);
		}
		if (check(R/i)) {
			updateMax(id, R/i);
		}
	}
	return fibonacci(id);
}