No.639 An Ordinary Sequence
レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 212
作問者 :
square1001
/ テスター :
WA_TLE
タグ : / 解いたユーザー数 212
作問者 :
square1001
/ テスター :
WA_TLE
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。