A5936. 「SNOI2020」取石子
编程题
NOI/NOI+/CTSC
知识点
题目描述
甲乙两个人玩取石子游戏。他们面前有一堆共 $n$ 个石子，然后由甲先手，两人轮流从中取走石子：甲第一次取走的个数不能超过 $k$，接下来每个人取走的个数不能超过上一个人刚刚取走个数的 $2$ 倍。每人每次必须至少取一个石子。取走最后一个石子的人失败，另一方获胜。现在已知 $k$，请你求出在 $1$ 到 $N$ 中有多少整数 $n$ 使得甲在 $n$ 颗石子的游戏中有必胜策略。
输入格式
多组数据。
第一行一个正整数 $T$ 表示数据组数。
接下来 $T$ 行每行两个用空格隔开的整数 $k, N$，表示一组询问。
第一行一个正整数 $T$ 表示数据组数。
接下来 $T$ 行每行两个用空格隔开的整数 $k, N$，表示一组询问。
输出格式
输出 $T$ 行，按照输入顺序，每行一个整数表示答案。
输入输出样例
输入 #1
3 1 5 2 5 1 10
输出 #1
2 3 4
说明/提示
对于所有数据，$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\%$ 的数据，无特殊限制。
- 对于 $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\%$ 的数据，无特殊限制。