三角数 $T_k$ とは、$k(k+1)/2$ の形の整数である。

$T_1 = 1$ や $T_8 = 36$ のように、平方数である三角数もいくつかある。しかし、二つの三角数の積を考えると、より多くの平方数が見つかる。例えば、$T_2 \cdot T_{24} = 3 \cdot 300 = 30^2$ である。

$n$ に関して、整数の3項組 $(a,b,c)$ で、$0 < c \leq n, c^2 = T_a \cdot T_b, 0 < a < b$ を満たす全てのものに対する $c$ の和を $S(n)$ としよう。 例えば、 $S(100) = \sqrt{T_1T_8} + \sqrt{T_2T_{24}} + \sqrt{T_1T_{49}} + \sqrt{T_3T_{48}} = 6 + 30 + 35 + 84 = 155$ である。

$S(10^5) = 1479802$, $S(10^9) = 241614948794$ が与えられる。

$S(10^{35}) \bmod 136101521$ を求めよ。

数列 $S_n$ を $S_0=290797, S_n={S_{n-1}}^2 \bmod 50515093 \; (n>0)$ によって定義する。

$0, 1, \dots, N-1$ の番号が振られたボウルがあり、はじめはボウル $n$ に $S_n$ 個の豆が入っている。

各ステップでは、ボウル $n$ に入った豆の個数がボウル $n+1$ に入った豆の個数よりも真に多いような最も小さい番号 $n$ を見つけ、ボウル $n$ からボウル $n+1$ に豆を1個移動させる。

ボウルに入った豆の個数が非減少な順にソートされるまでに必要なステップ数を $B(N)$ とする。 例えば、$B(5)=0, B(6)=14263289, B(100)=3284417556$ である。

$B(10^7)$ を求めよ。