Problem463 奇妙な漸化式

問題

すべての正整数に対し関数 f が以下のように定義されている:
●f(1) = 1
●f(3) = 3
●f(2n) = f(n)
●f(4n+1) = 2f(2n+1) - f(n)
●f(4n+3) = 3f(2n+1) - 2f(n)

 f(n) を関数 S(n) と定義する.

S(8) = 22, そして S(100) = 3604.
S(3の37乗) を求めよ. 回答は末尾9桁を答えよ.

ソース

実行結果

解説