QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 256 MB Total points: 100

# 6226. 取石子

统计

甲乙两个人玩取石子游戏。他们面前有一堆共 $n$ 个石子,然后由甲先手,两人轮流从中取走石子:甲第一次取走的个数不能超过 $k$,接下来每个人取走的个数不能超过上一个人刚刚取走个数的 $2$ 倍。每人每次必须至少取一个石子。取走最后一个石子的人失败,另一方获胜。现在已知 $k$,请你求出在 $1$ 到 $N$ 中有多少整数 $n$ 使得甲在 $n$ 颗石子的游戏中有必胜策略。

输入格式

多组数据。

第一行一个正整数 $T$ 表示数据组数。

接下来 $T$ 行每行两个用空格隔开的整数 $k, N$,表示一组询问。

输出格式

输出 $T$ 行,按照输入顺序,每行一个整数表示答案。

样例数据

样例输入

3
1 5
2 5
1 10

样例输出

2
3
4

样例解释

当 $k=1$ 时:

  • 如果 $n=1$,甲只能取走唯一一颗石子从而失败。
  • 如果 $n=2$,甲取走一颗石子,乙只能取走最后一颗石子,甲获胜。
  • 如果 $n=3$,甲只能取走一颗石子,乙再取走一颗石子,甲只能取走最后一颗石子从而失败。
  • 如果 $n=4$,甲只能取走一颗石子,乙再取走两颗石子,甲只能取走最后一颗石子从而失败。
  • 如果 $n=5$,甲只能取走一颗石子,乙只能取走一颗或两颗石子,甲总能再留给乙留下最后一颗石子从而获胜。

子任务

对于所有数据,$1\le T\le 10^5, k, N\le 10^{18}$。

  • 对于 $10\%$ 的数据,$T,N\le 500$。
  • 对于另外 $20\%$ 的数据,$T, N\le 10^5$。
  • 对于另外 $20\%$ 的数据,$T\le 3, N\le 3\times 10^6$。
  • 对于另外 $20\%$ 的数据,$k=1$。
  • 对于余下 $30\%$ 的数据,无特殊限制。