题目：

一个函数 \(f(x)\) 的定义为：

\[f(x)=\sum_{i=1}^{\lfloor \frac{x}{2}\rfloor}f(x-2 \times i)，x \ge 0 \]

特别地，\(f(0)=f(1)=1\)。

小 A 给你一个数 \(n\)，和一个质数 \(p\)，求出一个数 \(k\)，满足 \(f(k)\) 在模 \(p\) 的意义下的值最接近于 \(n\)。如果有多个 \(k\)，请输出最小的那个。

请注意，此处最接近的定义为：\(|f(k)\mod p-n|\) 最小。

解法：

关于模 \(p\)，是存在循环节的，周期为 \(p \times 2\)。在一个周期 \(T=p \times 2\) 中，每个可能的结果都会至少出现 \(1\) 次，所以我们只需要枚举 \(p\) 次，因为 \(f(x)\)（\(x\) 为偶数）和 \(f(x+1)\) 是相等的，判断哪个结果离 \(n\) 最接近，再记录最小位置即可。

时间复杂度 \(O(p \log p)\) 或 \(O(2p \log p)\)，可以通过。