← 返回题目列表

Codeforces · 1792/E

E. 除数和表

中文机器翻译题面 查看原题

给你一个 $$$n \times n$$$ 乘法表和一个正整数 $$$m = m_1 \cdot m_2$$$。 $$$n \times n$$$ 乘法表是一个包含 $$$n$$$ 行和 $$$n$$$ 列的表,编号从 $$$1$$$ 到 $$$n$$$,其中 $$$a_{i, j} = i \cdot j$$$。

对于 $$$m$$$ 的每个除数 $$$d$$$,检查:$$$d$$$ 在表中是否至少出现一次,如果出现,则包含 $$$d$$$ 的最小行是多少。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10$$$) — 测试用例的数量。

每个测试用例的第一行也是唯一一行包含三个整数 $$$n$$$、$$$m_1$$$ 和 $$$m_2$$$ ($$$1 \le n \le 10^9$$$; $$$1 \le m_1, m_2 \le 10^9$$$) - 乘法表的大小和整数 $$$m$$$ 表示为$$$m_1 \cdot m_2$$$。

输出

对于每个测试用例,令 $$$d_1, d_2, \dots, d_k$$$ 为 $$$m$$$ 的所有除数,并按升序排序。并令 $$$a_1, a_2, \dots, a_k$$$ 为答案数组,其中 $$$a_i$$$ 等于除数 $$$d_i$$$ 出现的最小行索引,或 $$$0$$$(如果没有这样的行)。

由于数组 $$$a$$$ 可能很大,因此首先打印一个整数 $$$s$$$ — $$$n \times n$$$ 表中存在的 $$$m$$$ 的除数数量。接下来,打印单个值 $$$X = a_1 \oplus a_2 \oplus \dots \oplus a_k$$$,其中 $$$\oplus$$$ 表示按位异或运算。

示例

输入 #1

3
3 72 1
10 10 15
6 1 210

输出 #1

6 2
10 0
8 5

注意

在第一个测试用例中, $$$m = 72 \cdot 1 = 72$$$ 并且有 $$$12$$$ 除数 $$$[1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72]$$$。 $$$3 \times 3$$$ 乘法表如下所示:

123112322463369

对于表中存在的 $$$m$$$ 的每个除数,标记具有最小行索引的位置。因此答案数组 $$$a$$$ 等于 $$$[1, 1, 1, 2, 2, 0, 3, 0, 0, 0, 0, 0]$$$。只有 $$$6$$$ 非零值,$$$a$$$ 的异或等于 $$$2$$$。

在第二个测试用例中, $$$m = 10 \cdot 15 = 150$$$ 并且有 $$$12$$$ 除数 $$$[1, 2, 3, 5, 6, 10, 15, 25, 30, 50, 75, 150]$$$。除 $$$75$$$ 和 $$$150$$$ 之外的所有除数都出现在 $$$10 \times 10$$$ 表中。数组 $$$a$$$ $$$=$$$ $$$[1, 1, 1, 1, 1, 1, 3, 5, 3, 5, 0, 0]$$$。有 $$$10$$$ 非零值,$$$a$$$ 的异或等于 $$$0$$$。

在第三个测试用例中, $$$m = 1 \cdot 210 = 210$$$ 并且有 $$$16$$$ 除数 $$$[1, 2, 3, 5, 6, 7, 10, 14, 15, 21, 30, 35, 42, 70, 105, 210]$$$。带有标记除数的 $$$6 \times 6$$$ 表如下所示:

1234561123456224681012336912151844812162024551015202530661218243036

数组 $$$a$$$ $$$=$$$ $$$[1, 1, 1, 1, 1, 0, 2, 0, 3, 0, 5, 0, 0, 0, 0, 0]$$$。有 $$$8$$$ 非零值,$$$a$$$ 的异或等于 $$$5$$$。