English · Original
Chinese · Translation
Formal · Original
Harry came to know from Dumbledore that Salazar Slytherin's locket is a horcrux. This locket was present earlier at 12 Grimmauld Place, the home of Sirius Black's mother. It was stolen from there and is now present in the Ministry of Magic in the office of Dolorous Umbridge, Harry's former Defense Against the Dark Arts teacher.
Harry, Ron and Hermione are infiltrating the Ministry. Upon reaching Umbridge's office, they observed a code lock with a puzzle asking them to calculate count of magic numbers between two integers _l_ and _r_ (both inclusive).
Harry remembered from his detention time with Umbridge that she defined a magic number as a number which when converted to a given base _b_, all the digits from 0 to _b_ - 1 appear even number of times in its representation without any leading zeros.
You have to answer _q_ queries to unlock the office. Each query has three integers _b__i_, _l__i_ and _r__i_, the base and the range for which you have to find the count of magic numbers.
## Input
First line of input contains _q_ (1 ≤ _q_ ≤ 105) — number of queries.
Each of the next _q_ lines contain three space separated integers _b__i_, _l__i_, _r__i_ (2 ≤ _b__i_ ≤ 10, 1 ≤ _l__i_ ≤ _r__i_ ≤ 1018).
## Output
You have to output _q_ lines, each containing a single integer, the answer to the corresponding query.
[samples]
## Note
In sample test case 1, for first query, when we convert numbers 4 to 9 into base 2, we get:
* 4 = 1002,
* 5 = 1012,
* 6 = 1102,
* 7 = 1112,
* 8 = 10002,
* 9 = 10012.
Out of these, only base 2 representation of 9 has even number of 1 and 0. Thus, the answer is 1.
哈利从邓布利多那里得知，萨拉查·斯莱特林的挂坠是一个魂器。这个挂坠此前位于格里莫广场12号，即小天狼星·布莱克母亲的家。它被从那里偷走，现在位于魔法部多洛雷斯·乌姆里奇的办公室内，而乌姆里奇正是哈利的前黑魔法防御术老师。
哈利、罗恩和赫敏潜入了魔法部。当他们到达乌姆里奇的办公室时，发现了一个密码锁，上面有一个谜题，要求他们计算在两个整数 #cf_span[l] 和 #cf_span[r]（包含两端）之间有多少个“魔法数”。
哈利回忆起在乌姆里奇那里接受处罚时，她定义了一个“魔法数”：一个数在转换为给定进制 #cf_span[b] 后，其表示中（不含前导零）从 #cf_span[0] 到 #cf_span[b - 1] 的每一个数字都出现偶数次。
你需要回答 #cf_span[q] 个查询以解锁办公室。每个查询包含三个整数 #cf_span[bi]、#cf_span[li] 和 #cf_span[ri]，分别表示进制和需要统计魔法数的区间范围。
输入的第一行包含 #cf_span[q]（#cf_span[1 ≤ q ≤ 105]）——查询的数量。
接下来的 #cf_span[q] 行，每行包含三个用空格分隔的整数 #cf_span[bi]、#cf_span[li]、#cf_span[ri]（#cf_span[2 ≤ bi ≤ 10]，#cf_span[1 ≤ li ≤ ri ≤ 1018]）。
你必须输出 #cf_span[q] 行，每行包含一个整数，对应每个查询的答案。
在样例测试用例 #cf_span[1] 中，对于第一个查询，当我们将数字 #cf_span[4] 到 #cf_span[9] 转换为二进制时，得到：
其中，只有 #cf_span[9] 的二进制表示具有偶数个 #cf_span[1] 和 #cf_span[0]。因此，答案是 #cf_span[1]。
## Input
输入的第一行包含 #cf_span[q]（#cf_span[1 ≤ q ≤ 105]）——查询的数量。接下来的 #cf_span[q] 行，每行包含三个用空格分隔的整数 #cf_span[bi]、#cf_span[li]、#cf_span[ri]（#cf_span[2 ≤ bi ≤ 10]，#cf_span[1 ≤ li ≤ ri ≤ 1018]）。
## Output
你必须输出 #cf_span[q] 行，每行包含一个整数，对应每个查询的答案。
[samples]
## Note
在样例测试用例 #cf_span[1] 中，对于第一个查询，当我们将数字 #cf_span[4] 到 #cf_span[9] 转换为二进制时，得到： #cf_span[4 = 100_2]， #cf_span[5 = 101_2]， #cf_span[6 = 110_2]， #cf_span[7 = 111_2]， #cf_span[8 = 1000_2]， #cf_span[9 = 1001_2]。其中，只有 #cf_span[9] 的二进制表示具有偶数个 #cf_span[1] 和 #cf_span[0]。因此，答案是 #cf_span[1]。
**Definitions**
Let $ q \in \mathbb{Z} $ be the number of queries.
For each query $ i \in \{1, \dots, q\} $:
- $ b_i \in \mathbb{Z} $, $ 2 \le b_i \le 10 $, is the base.
- $ l_i, r_i \in \mathbb{Z} $, $ 1 \le l_i \le r_i \le 10^{18} $, define the range $ [l_i, r_i] $.
A number $ n \in \mathbb{Z}^+ $ is a *magic number* in base $ b $ if, in its base-$ b $ representation (without leading zeros), every digit $ d \in \{0, 1, \dots, b-1\} $ appears an even number of times (including zero).
**Constraints**
1. $ 1 \le q \le 10^5 $
2. $ 2 \le b_i \le 10 $ for all $ i $
3. $ 1 \le l_i \le r_i \le 10^{18} $ for all $ i $
**Objective**
For each query $ i $, compute:
$$
\left| \left\{ n \in [l_i, r_i] \,\middle|\, \text{in base } b_i, \text{ every digit } d \in \{0,1,\dots,b_i-1\} \text{ appears an even number of times in } \mathrm{repr}_{b_i}(n) \right\} \right|
$$
API Response (JSON)
{
"problem": {
"name": "E. Salazar Slytherin's Locket",
"description": {
"content": "Harry came to know from Dumbledore that Salazar Slytherin's locket is a horcrux. This locket was present earlier at 12 Grimmauld Place, the home of Sirius Black's mother. It was stolen from there and ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF855E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Harry came to know from Dumbledore that Salazar Slytherin's locket is a horcrux. This locket was present earlier at 12 Grimmauld Place, the home of Sirius Black's mother. It was stolen from there and ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "哈利从邓布利多那里得知，萨拉查·斯莱特林的挂坠是一个魂器。这个挂坠此前位于格里莫广场12号，即小天狼星·布莱克母亲的家。它被从那里偷走，现在位于魔法部多洛雷斯·乌姆里奇的办公室内，而乌姆里奇正是哈利的前黑魔法防御术老师。\n\n哈利、罗恩和赫敏潜入了魔法部。当他们到达乌姆里奇的办公室时，发现了一个密码锁，上面有一个谜题，要求他们计算在两个整数 #cf_span[l] 和 #cf_span[r]（包含两...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ q \\in \\mathbb{Z} $ be the number of queries. \nFor each query $ i \\in \\{1, \\dots, q\\} $: \n- $ b_i \\in \\mathbb{Z} $, $ 2 \\le b_i \\le 10 $, is the base. \n- $ l_i, r_i \\in \\math...",
"is_translate": false,
"language": "Formal"
}
]
}