本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-24 16:35:51

:::::info[题目基本信息] 考察：数学，博弈论，数位 DP（NOI/NOI+/CTSC）。
题目简介：
$T$ 组数据，每组数据给定 $N,K$，定义正整数对 $(n,k)$ 合法（不合法）为：

• $\forall i\ge 1,(1,i)$ 不合法。
• $\forall n>1,\exist i\in[1,\min(n-1,k)],(n-i,2i)$ 不合法则 $(n,k)$ 合法，否则不合法。

求有多少正整数 $n\le N$，满足 $(n,K)$ 合法。
数据范围：

• $1\le T\le 10^5$
• $1\le N,K\le 10^{18}$

时间限制：1s。
空间限制：180MB。
::::: 齐肯多夫定理相关博弈板子题，引入齐肯多夫定理：
:::::success[齐肯多夫定理讲解] 齐肯多夫定理：$\forall n\in\mathbb Z_+,\exist k\in\mathbb Z_+,\exist\{id_k\}$ 满足：

• $\forall i\in[1,k-1],id_i+1<id_{i+1}$。
• $\displaystyle\sum_{i=1}^kf_{id_i}=n$，其中 $f_i$ 表示斐波那契数列的第 $i$ 项。

::::success[证明] 考虑数学归纳法：
若 $\exist p\in\mathbb Z_+,f_p=n$，则显然成立。
否则，设 $f_p<n<f_{p+1}$，递归 $n-f_p$ 的子问题，容易发现 $f_{p-1}>n-f_p$，所以不会取到相邻的斐波那契数，同时由于数一直在不断减小，所以最终一定能转化成第 $1$ 种情况。
:::: ::::: 对于本题，容易发现先手全取完一定能赢，所以我们不妨钦定先手不能先取完。
对 $n$ 分类讨论：

• $\exist p\in\mathbb Z_+,f_p=n$：
  这时先手必败。 :::::success[证明] 设 $(n-i,2i)$ 为它的后继状态。
• 当 $i\ge f_{p-2}$ 时，后手直接全取完就赢了。
• 在 $n=1$ 时，先手都取不了，必败。
• 在 $n=2$ 时，先手同样必败。
• 在 $i<f_{p-2}$ 的其他情况时，归纳假设后手能在 $f_{p-2}$ 的子问题获胜，然后递归到 $f_{p-1}$ 的子问题，先手唯一希望是取完 $f_{p-1}$，但是不可能，因为后手最后一手取的不超过 $\dfrac{2}{3}f_{p-2}$，由于有定理： $$\frac{4}{3}f_{x}<f_{x+1}$$ ::::success[证明] $$\frac{4}{3}f_x<f_{x+1}\\Leftrightarrow\frac{4}{3}f_x<f_{x-1}+f_x\\Leftrightarrow\frac{1}{3}f_x<f_{x-1}\\Leftrightarrow\frac{1}{3}(f_{x-1}+f_{x-2})<f_{x-1}\\Leftrightarrow\frac{1}{3}f_{x-2}<\frac{2}{3}f_{x-1}\\Leftrightarrow f_{x-2}<2f_{x-1}$$ 显然成立。
  :::: :::::
• 对于其他情况，答案就为 $f_{id_1}$。 :::::success[证明] 先证明 $[1,f_{id_1})$ 的数不合法，这时 $f_{id_1}$ 的子问题后手胜利，套用上面的结论，后面的数均为后手胜利，所以先手必败。
  $f_{id_1}$ 合法的原因也类似。
  ::::: 这时我们直接枚举 $n$ 判断合法性会 TLE，考虑 Fib 位数位 DP。
  设 $dp_{x,0/1,0/1}$ 表示考虑到第 $x$ 位，前面是否选了任何一个 $f_p$，同时上一位选没选。
  转移是平凡的，在 $f_p$ 小于等于 $k$ 的时候后面直接全填 $0$ 就可以得出先手必败的数量（记得要判 $0$）。
  然后容斥以下就行。 时间复杂度为 $\Theta(T\log n)$，空间复杂度为 $\Theta(\log n)$。

code