ウクーニャたんお誕生日コンテスト: A - UkuNumber
問題
A: UkuNumber - ウクーニャたんお誕生日コンテスト | AtCoder
解説
まず、は確定する。これについて自分はのうち一方をで固定し、他方を動かす実験を行い発見したが、Editorialによると「自明な解から考える」ことより導ける。
次に、確定していない変数を利用して、うく数列を書き下す。
変数の項の係数と定数の項について、それぞれはフィボナッチ数列で表される。数列の第2項目から考えると、一般項は以下のようになる。
よって、先にフィボナッチ数列を計算しておき、入力に対しての値を計算すれば良い。 フィボナッチ数列は、int64がオーバーフローするギリギリくらいまで計算しても項数は100以内に収まるため、各ケースについてフィボナッチ数列を初項から辿れば良い。
解説
int main() { int64_t f[120]; set<int> fset; f[0] = 0, f[1] = 1; fset.insert(0); fset.insert(1); rep(i, 91) { f[i + 2] = f[i + 1] + f[i]; fset.insert(f[i + 2]); } int T; cin >> T; rep(i, T) { int64_t x; cin >> x; if (fset.count(x)) { cout << "1 1\n"; continue; } int64_t ans = x - 1; rep(ki, 91) { if ((x - f[ki]) % f[ki + 1]) continue; auto b = (x - f[ki]) / f[ki + 1]; ans = min(ans, b); } cout << "1 " << ans << "\n"; } }