1853B.md (2077B)
1 Source: https://codeforces.com/problemset/problem/1853/B 2 3 B. Fibonaccharsis 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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. 22 23 A sequence of non-decreasing non-negative integers is considered fibonacci-like if $f_i = f_{i-1} + f_{i-2}$ for all $i \gt 2$, where $f_i$ denotes the $i$-th element in the sequence. Note that $f_1$ and $f_2$ can be arbitrary. 24 25 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. 26 27 Impress Ntarsis by helping him with this task. 28 29 Input 30 31 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. 32 33 Each test case contains two integers, $n$ and $k$ ($1 \leq n \leq 2 \cdot 10^5$, $3 \leq k \leq 10^9$). 34 35 It is guaranteed the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 36 37 Output 38 39 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. 40 41 Example 42 43 Input 44 45 ``` 46 8 47 48 22 4 49 50 3 9 51 52 55 11 53 54 42069 6 55 56 69420 4 57 58 69 1434 59 60 1 3 61 62 1 4 63 ``` 64 65 Output 66 67 ``` 68 4 69 0 70 1 71 1052 72 11571 73 0 74 1 75 0 76 ``` 77 78 Note 79 80 There are $4$ valid fibonacci-like sequences for $n = 22$, $k = 4$: 81 82 * $[6,8,14,22]$, 83 * $[4,9,13,22]$, 84 * $[2,10,12,22]$, 85 * $[0,11,11,22]$. 86 87 For $n = 3$, $k = 9$, it can be shown that there are no fibonacci-like sequences satisfying the given conditions. 88 89 For $n = 55$, $k = 11$, $[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]$ is the only fibonacci-like sequence.