CF855E Salazar Slytherin's Locket

哈利从邓布利多那里得知，萨拉查·斯莱特林的挂坠盒是魂器。这个挂坠盒曾经在小天狼星·布莱克母亲的住所——格里莫广场12号。后来它从那里被偷走，如今在魔法部多洛雷斯·乌姆里奇的办公室中。乌姆里奇曾是哈利的黑魔法防御术老师。 哈利、罗恩和赫敏正潜入魔法部。当他们到达乌姆里奇的办公室时，发现一道密码锁，上面的问题是请他们计算区间 $l$ 到 $r$（包含两端）中“魔法数”的个数。 哈利回忆起曾在乌姆里奇的禁闭期间，她曾定义“魔法数”为如下性质的数字：将一个数转换为给定进制 $b$ 后，其表示中，从 $0$ 到 $b-1$ 的所有数字都恰好出现偶数次（无前导零）。 现在你需要回答 $q$ 个查询以解锁办公室。每个查询给定进制和区间 $\left[b_{i},l_{i},r_{i}\right]$ ，求在指定区间内满足条件的“魔法数”的个数。

第一行输入一个整数 $q$（$1 \leq q \leq 10^{5}$）——表示查询的个数。 接下来 $q$ 行，每行包含三个以空格分隔的整数 $b_{i}$、$l_{i}$、$r_{i}$（$2 \leq b_{i} \leq 10$，$1 \leq l_{i} \leq r_{i} \leq 10^{18}$）。

输出 $q$ 行，每行一个整数，表示对应查询的答案。

在样例测试 $1$ 中，对第一个查询，将 $4$ 到 $9$ 转换为二进制，得到： - $4=100_2$， - $5=101_2$， - $6=110_2$， - $7=111_2$， - $8=1000_2$， - $9=1001_2$。 其中，只有 $9$ 的二进制表示中 $0$ 和 $1$ 的出现次数均为偶数。因此，答案为 $1$。 由 ChatGPT 5 翻译