No.2989 Fibonacci Prize
potato167問題文最終更新日: 2024-12-13 21:59:52
問題文
PotaToder Japan Open 決勝の賞金を決めることになった俺。賞金はフィボナッチ数列の区間を取り出すことに。賞金の総和が自分の好きな整数の倍数だと綺麗で嬉しい！予算の上限以下でそのような区間はいくつあるんだろうか？
数列 $f = (f_{1}, f_{2}, \cdots)$ を以下が全て成り立つ数列と定義します。
- $f_{1} = 1$
- $f_{2} = 1$
- $3$ 以上の整数 $i$ に対して $f_{i} = f_{i - 1} + f_{i - 2}$
正整数 $N, M$ が与えられます。以下の条件を全て満たす整数 $(L, R)$ の組の数を出力してください。
- $1\leq L \leq R$
- $f_{L} + f_{L + 1} + \cdots + f_{R}$ が $N$ の倍数
- $f_{L} + f_{L + 1} + \cdots + f_{R} \leq f_{M}$
制約
- $1\leq N\leq 2\times 10^{5}$
- $1\leq M\leq 2\times 10^{9}$
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられます。
$N$ $M$
出力
答えを出力してください。
サンプル
サンプル1
入力
50 10
出力
1
$(L, R) = (4, 8)$ とします。
$f_{4} + f_{5} + f_{6} + f_{7} + f_{8} = 3 + 5 + 8 + 13 + 21 = 50$ となり、これは $N$ の倍数で $f_{M} = 55$ 以下であるため条件を満たします。条件を満たす $(L, R)$ の組はこれだけなので $1$ を出力します。
サンプル2
入力
1 2
出力
2
$(L, R) = (1, 1), (2, 2)$ は区別します。
サンプル3
入力
167924 924924167
出力
10163382327065
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。