問題一覧 > 通常問題

No.2989 Fibonacci Prize

レベル : / AI推定難易度 : 2000 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 28
作問者 : 👑 potato167
お気に入りにしたユーザー ProblemId : 11708 / 自分の提出
問題文最終更新日: 2025-09-06 00:31:23
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
Advent Calendar Contest 2024 (順位表) の他の問題:

Story

I am the one who has to decide the prize money for the PotaToder Japan Open finals. The prizes will be taken from an interval of the Fibonacci sequence. It would be neat and make me happy if the total prize money were a multiple of my favorite integer! How many such intervals are there within the upper limit of the budget?

Problem Statement

Define the sequence $f = (f_{1}, f_{2}, \cdots)$ as the sequence satisfying all of the following.

  • $f_{1} = 1$
  • $f_{2} = 1$
  • For every integer $i$ greater than or equal to $3$, $f_{i} = f_{i - 1} + f_{i - 2}$

You are given positive integers $N, M$. Output the number of pairs of integers $(L, R)$ satisfying all of the following conditions.

  • $1\leq L \leq R$
  • $f_{L} + f_{L + 1} + \cdots + f_{R}$ is a multiple of $N$
  • $f_{L} + f_{L + 1} + \cdots + f_{R} \leq f_{M}$

Constraints

  • $1\leq N\leq 2\times 10^{5}$
  • $1\leq M\leq 2\times 10^{9}$
  • All input values are integers

Input

The input is given from standard input in the following format.

$N$ $M$

Output

Output the answer.

Sample

Sample 1
Input
50 10
Output
1

Let $(L, R) = (4, 8)$.

Then $f_{4} + f_{5} + f_{6} + f_{7} + f_{8} = 3 + 5 + 8 + 13 + 21 = 50$, which is a multiple of $N$ and is at most $f_{M} = 55$, so the conditions are satisfied. This is the only pair $(L, R)$ satisfying the conditions, so output $1$.

Sample 2
Input
1 2
Output
2

$(L, R) = (1, 1), (2, 2)$ are distinguished.

Sample 3
Input
167924 924924167
Output
10163382327065

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