No.639 An Ordinary Sequence
タグ : / 解いたユーザー数 221
作問者 :
WA_TLE
Problem Statement
You are given an integer $N$. Find the $N$-th term $a_N$ of the sequence $a$ defined by $a_0 = 1$, $a_i = a_{\lfloor i/3 \rfloor} + a_{\lfloor i/5 \rfloor}$. Here, for a real number $x$ greater than or equal to $0$, $\lfloor x \rfloor$ denotes the integer part of $x$.
Input
$N$
An integer $N (0 \le N \le 10^{18})$ is given.
Output
Print $a_N$ on the first line.
Print a newline at the end.
Sample
Sample 1
Input
7
Output
4
We have $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$.
Sample 2
Input
1000000000000000000
Output
3207281389
This is the case where $N$ is at its maximum.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。