ウクーニャたんお誕生日コンテスト: A - UkuNumber

問題

A: UkuNumber - ウクーニャたんお誕生日コンテスト | AtCoder

解説

まず、は確定する。これについて自分はのうち一方をで固定し、他方を動かす実験を行い発見したが、Editorialによると「自明な解から考える」ことより導ける。

次に、確定していない変数を利用して、うく数列を書き下す。

変数の項の係数と定数の項について、それぞれはフィボナッチ数列で表される。数列の第２項目から考えると、一般項は以下のようになる。

よって、先にフィボナッチ数列を計算しておき、入力に対しての値を計算すれば良い。 フィボナッチ数列は、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";
  }
}