概要
考察重視の問題です．
問題原案：@uni_kakurenbo
解説
愚直な実装
問題文の定義通りに関数 を実装するところから始めてみましょう．
たとえば Python では次のようなコードで表現できます．
さらに，この式には足し算のみが登場しますので，あまりを取るという操作を計算の途中に行うことができます．(証明などは他サイト等へ委ねます．)
これを考慮すると以下のように書き換えることができます．
再帰のメモ化と動的計画法
先述した愚直な実装における時間計算量を見積もってみましょう．
先の実装では，どんな入力に対しても最終的に の足し算のみに分解されます．
つまり を求めるために 回 が足されることになるのです．
したがって，テストケースあたりの時間計算量は になります．
試しに，サンプル項のビジュアライザを用いて の値を計算してみると，いとも簡単に 付近を突破してしまうことがわかるでしょう．
これでは の入力に対して到底時間内に答えを出すことはできません．
メモ化
解決策の一つとして「メモ化」があります．
答えの求め方をよく考えてみると，何度も同じ引数で関数 の値を計算していることがわかります．
たとえば
のようになります．
よって，一度値を求めた組 についてはその答えを「メモ」しておくことで，大幅に計算量を削減することができます．
これを「メモ化」と呼び，メモ化がされた再帰を「メモ化再帰」と呼んだりもします．
また，複数のテストケースについての答えを求めるため，やはりメモ化によって計算量の大幅な削減が期待できます．
動的計画法
実は，Python などの動作が比較的遅い一部の言語では，先述したメモ化再帰を用いて解くことができません．
代わりに動的計画法を用いて実装してみましょう．
「動的計画法」と聞くと難しい印象を受ける方もいらっしゃるかもしれませんが，本質は「より小さい問題の答えを用いて，大きな問題の答えを求める」ことです．
今回は，より小さい問題 の答えを用いて，大きな問題 の答えを求める方法を考えてみましょう．
実は，こちらも問題文に与えられている式を"そのまま"利用することができます．
Python での実装例を次に示します．
これをあらかじめ求めておけば，各テストケースについて で答えることができます．
これで [Easy] が解けました．
漸化式の効率化
の最大値をそれぞれ とすると，
先述の解法では，問題全体を通して少なくとも 回は計算を行わなくてはなりません．
[Easy] では が保証されているため十分に間に合いますが，[Hard] の制約下では TLE となってしまうでしょう．
そこで，もっと効率的に の値を求めることはできないか考えてみましょう．
の定義となっている漸化式を変形していきます．
結果的に， を の二つを用いて表すことができました．
これを先述したメモ化再帰や動的計画法で実装すればよいです．(Python の場合は依然として前者では間に合いません．)
これで [Hard] が解けました．
発展
類題
(難易度順)