問題一覧 > 通常問題

No.639 An Ordinary Sequence

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 157
作問者 : square1001square1001 / テスター : WA_TLEWA_TLE
5 ProblemId : 1805 / 出題時の順位表
問題文最終更新日: 2017-08-17 09:53:58

問題文

整数 $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$ が最大となるケースです。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。