No.639 An Ordinary Sequence

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 99
作問者 : square1001square1001 / テスター : WA_TLEWA_TLE
3 ProblemId : 1805 / 出題時の順位表

問題文

整数 $N$ が与えられます。$a_0 = 1$, $a_i = a_{\lfloor i/3 \rfloor} + a_{\lfloor i/5 \rfloor}$. で定義される数列 $a$ の第 $N$ 項 $a_N$ を求めなさい。ただし、$0$ 以上の実数 $x$ に対して $\lfloor x \rfloor$ は $x$ の整数部分を表すものとします。

入力

$N$

整数 $N (0 \le N \le 10^{18})$ が与えられます。

出力

1行目に $a_N$ を出力してください。
最後に改行してください。

サンプル

サンプル1
入力
7
出力
4

$a_7 = a_{\lfloor 7/3 \rfloor} + a_{\lfloor 7/5 \rfloor} = a_1 + a_2 = (a_{\lfloor 1/3 \rfloor} + a_{\lfloor 1/5 \rfloor}) + (a_{\lfloor 2/3 \rfloor} + a_{\lfloor 2/5 \rfloor}) = (a_0 + a_0) + (a_0 + a_0) = (1 + 1) + (1 + 1) = 4$ となります。

サンプル2
入力
1000000000000000000
出力
3207281389

これは $N$ が最大となるケースです。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。