题意

先手不能取走超过 $k$ 个棋子，后面每次取石子都不能超过上次石子数的 2 倍，取走最后一个石子的人为输，然后问 $1\sim N$ 中有多少个整数能让先手是必胜态的。每组测试点有 $10^5$ 组数据。

前置知识 : Fibonacci 博弈

首先看到“每次取石子都不能超过上次石子数的 2 倍”就能想到是 Fibonacci 博弈。如果总石子数是 $n$ ，只规定第一次取走的数不能超过 $n-1$ ，我们考虑拿走最后一个石子的人获胜的话，那么结论就是 ：只要 $n$ 是斐波那契数，那么先手必败；反之就是先手必胜。

$n$ 是斐波那契数时先手必败的证明

$n=1$ 时暂且不管，$n=2,3$ 时必败（也就是斐波那契数的 $f_2,f_3$）。

如果 $i\ge 4,~ n=f_i=f_{i-1}+f_{i-2},~2f_{i-2}>f_{i-1}$ 。

• 如果先手取大于等于 $f_{i-2}$ 个石子，那么后手就能直接拿完剩下的所有石子。
• 如果先手取小于 $f_{i-2}$ 个石子，那么问题就变成了谁先拿完 $f_{i-2}$ 胜（后面变成 $f_{i-1}$ 的话先手必输）而拿完 $f_{i-2}$ 也是先手必败，所以先手必败。

$n$ 不是斐波那契数时先手必胜的证明

首先介绍 齐肯多夫定理 : 任意正整数 $n$ 都可以倍表示成若干个不连续的斐波那契数之和。

也就是说例如 $n=\sum\limits_{i=1}^k f_{a_i}$ ，那么一定有 $a_1+1<a_2,~a_2+1<a_3,…$

那么设 $n=f_{a_1}+…,$ 且满足 $a_1+1<a_2,~a_2+1<a_3,…$ 所以 $2f_{a_{i-1}}<f_{a_i}$ 。如果此时不是斐波那契数，先手拿完了 $f_{a_1}$ 那么后手就不可能拿完 $f_{a_2}$ 。类似地后手也不可能任何一种 $f_{a_i}$ 拿完，最后一定是先手拿完。

如果第一次可以拿 $n$ 个石子，那么先手第一次最少拿多少石子会获胜？

首先 $n$ 是斐波那契数时，直接全都拿走先手就赢了。而如果不是斐波那契数的话，就像上面这个先手必胜证明一样，$n$ 是若干个不相邻的斐波那契数之和，取其中最小的那个斐波那契数，也就是 $f_{a_1}$ 就行了。

回到本题

1.如何处理”拿走最后一个石子必败” ？

那么就变成了大家谁也不想拿到最后一个石子。那么策略就变成了尽可能把最后一个子剩下，但是谁先拿到倒数第二个石子，谁就赢了。所以“$n$ 个石子取走最后一个输”问题就变成了“$n-1$ 个石子取走最后一个赢”，就重新回到斐波那契博弈的问题上来了。

那么整个问题就变成了，$1\sim N-1$ 当中有多少个 $n$ 能让先手取走最后一个石子达成必胜了。（$0$ 的话显然，由于第一次不能不取，放在原题里先手取完就输了）。

2.如何处理先手第一次取石子不超过 $k$ ？

根据前置知识，我们知道只要先手第一次取 $n$ 写成斐波那契数求和当中，最小的那个斐波那契数就一定能赢。那么正难则反，我们考虑 $1\sim n-1$ 当中，先手第一次取的最小斐波那契数大于 $k$ 时有多少个。然后用 $n-1$ 减去它就行了。

暴力枚举我们肯定是跑不完的，所以我们考虑数位 DP

3.类数位 DP 的处理

假设在二进制下的 0/1 表示这个数的构成中是否有 $2^i$ ，那么斐波那契数一样可以拆成这么多数位，第 $i$ 位的 0/1 表示这个数的构成是否有 $f_i$ 。根据齐肯多夫定理，每个数拆完之后的数位一定没有两个相邻的 1 。

然后我们考虑对 $n-1$ 做数位 DP 记搜，一共三个状态 : 当前数位是第几位，是否有小于等于 $n-1$ 的限制（没有这个限制就是全部结果都算上），前一位的数位是什么。那么初始搜索可以定位 dfs(90, 1, 0) （其中定 90 个数位是因为设 $f_1=1,f_2=2$ 时，第 90 个数一定大于 $10^{18}$）。

每次搜索当前位的组数时，显然就是考虑当前位记录为 0/1 时搜索回溯的结果总和。

• 如果当前位定做 $0$ 往下搜，如果 $n-1$ 的当前数位是 0 ，那么依旧要加上小于等于 $n-1$ 的限制，反之则不需要。
• 如果当前数位是 $1$ ，或者当前没有小于等于的限制，那可以把当前数位当做 1 再往下搜一次。保持限制即可。
• 每次只将没有做限制、且前一位是 $0$ 的情况记录下来（因为其他情况的数字都可能会变动）
• 我们记录大于 $k$ 的最小斐波那契数为 $x$ ，如果当前搜索位小于 $x$ ，则必须返回 $1$ 。因为此时前 $x-1$ 位的填写情况必须是 $0$ 。

最终返回的结果还要再减去 $1$ ，然后再让 $n-1$ 减。因为不难得到上面这个结果会把全 $0$ 的情况也算进去。

代码

const int F = 90;
i64 fibo[F + 5];
void build_fibo()
{
    fibo[1] = 1, fibo[2] = 2;
    for (int i = 3; i <= 90; ++i)
        fibo[i] = fibo[i - 1] + fibo[i - 2];

}

int T;
i64 k, n, tmpn;
int target;

i64 dp[F]; 
int a[F];
i64 dfs(int pos, int full, int pre)
{
    if (pos < target)
        return 1;
    if (!full && !pre && dp[pos] >= 0)
        return dp[pos];
    i64 ret = dfs(pos - 1, full && (a[pos] == 0), 0);
    if (pre == 0 && (a[pos] == 1 || full == 0))
        ret += dfs(pos - 1, full, 1);
    if (pre == 0 && full == 0)
        dp[pos] = ret;
    return ret;
}
void solve()
{
    scanf("%lld%lld", &k, &n), --n;
    memset(dp, -1, sizeof(dp)), memset(a, 0, sizeof(a));
    target = 91, tmpn = n;
    for (int i = 90; i; --i)
        if (fibo[i] > k)
            target = i;
    for (int i = 90; i; --i)
        if (tmpn >= fibo[i])
            tmpn -= fibo[i], a[i] = 1;
    printf("%lld\n", n - dfs(90, 1, 0) + 1);
}

int main()
{
    build_fibo();
    scanf("%d", &T);
    while (T--)
        solve();
}