問題一覧 > 通常問題

No.639 An Ordinary Sequence

レベル : / AI推定難易度 : 750 / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 221
作問者 : square1001 / テスター : WA_TLE
お気に入りにしたユーザー ProblemId : 1805 / 自分の提出
問題文最終更新日: 2026-06-25 04:45:58
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 181 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。