Preparando MOJI
Ntarsis has received two integers $$$n$$$ and $$$k$$$ for his birthday. He wonders how many fibonacci-like sequences of length $$$k$$$ can be formed with $$$n$$$ as the $$$k$$$-th element of the sequence.
A sequence of non-decreasing non-negative integers is considered fibonacci-like if $$$f_i = f_{i-1} + f_{i-2}$$$ for all $$$i > 2$$$, where $$$f_i$$$ denotes the $$$i$$$-th element in the sequence. Note that $$$f_1$$$ and $$$f_2$$$ can be arbitrary.
For example, sequences such as $$$[4,5,9,14]$$$ and $$$[0,1,1]$$$ are considered fibonacci-like sequences, while $$$[0,0,0,1,1]$$$, $$$[1, 2, 1, 3]$$$, and $$$[-1,-1,-2]$$$ are not: the first two do not always satisfy $$$f_i = f_{i-1} + f_{i-2}$$$, the latter does not satisfy that the elements are non-negative.
Impress Ntarsis by helping him with this task.
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^5$$$), the number of test cases. The description of each test case is as follows.
Each test case contains two integers, $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$3 \leq k \leq 10^9$$$).
It is guaranteed the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case output an integer, the number of fibonacci-like sequences of length $$$k$$$ such that the $$$k$$$-th element in the sequence is $$$n$$$. That is, output the number of sequences $$$f$$$ of length $$$k$$$ so $$$f$$$ is a fibonacci-like sequence and $$$f_k = n$$$. It can be shown this number is finite.
822 43 955 1142069 669420 469 14341 31 4
4 0 1 1052 11571 0 1 0
There are $$$4$$$ valid fibonacci-like sequences for $$$n = 22$$$, $$$k = 4$$$:
For $$$n = 3$$$, $$$k = 9$$$, it can be shown that there are no fibonacci-like sequences satisfying the given conditions.
For $$$n = 55$$$, $$$k = 11$$$, $$$[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]$$$ is the only fibonacci-like sequence.
Informação
Provedor Codeforces
Código CF1853B
Tags
Submetido 0
BOUA! 0
Taxa de BOUA's 0%
Datas 09/05/2023 10:41:07
Relacionados