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