CF1792E.Divisors and Table

You are given an $n \times n$ multiplication table and a positive integer $m = m_1 \cdot m_2$. A $n \times n$ multiplication table is a table with $n$ rows and $n$ columns numbered from $1$ to $n$, where $a_{i, j} = i \cdot j$.

For each divisor $d$ of $m$, check: does $d$ occur in the table at least once, and if it does, what is the minimum row that contains $d$.

给你一个 $n \times n$ 的乘法表和一个正整数 $m = m_1 \cdot m_2$。一个 $n \times n$ 的乘法表是一个具有 $n$ 行和 $n$ 列的表格，行列编号均从 $1$ 到 $n$，其中第 $i$ 行第 $j$ 列的元素为 $a_{i, j} = i \cdot j$。

对 $m$ 的每个正因数 $d$，请判断：$d$ 是否至少在该表中出现一次；若出现，求出包含 $d$ 的最小行号。

The first line contains a single integer $t$ ($1 \le t \le 10$) — the number of test cases.

The first and only line of each test case contains three integers $n$, $m_1$ and $m_2$ ($1 \le n \le 10^9$; $1 \le m_1, m_2 \le 10^9$) — the size of the multiplication table and the integer $m$ represented as $m_1 \cdot m_2$.

第一行包含一个整数 $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$ 形式给出的整数 $m$。

For each test case, let $d_1, d_2, \dots, d_k$ be all divisors of $m$ sorted in the increasing order. And let $a_1, a_2, \dots, a_k$ be an array of answers, where $a_i$ is equal to the minimum row index where divisor $d_i$ occurs, or $0$, if there is no such row.

Since array $a$ may be large, first, print an integer $s$ — the number of divisors of $m$ that are present in the $n \times n$ table. Next, print a single value $X = a_1 \oplus a_2 \oplus \dots \oplus a_k$, where $\oplus$ denotes the bitwise XOR operation.

对于每个测试用例，设 $d_1, d_2, \dots, d_k$ 为 $m$ 的所有正因数，并按升序排列。再设 $a_1, a_2, \dots, a_k$ 为一个答案数组，其中 $a_i$ 表示因数 $d_i$ 首次出现的最小行号；若该因数在表中不存在，则 $a_i = 0$。

由于数组 $a$ 可能很长，首先输出一个整数 $s$ —— 即在 $n \times n$ 表中实际出现的 $m$ 的因数的个数。接着，输出单个值 $X = a_1 \oplus a_2 \oplus \dots \oplus a_k$，其中 $\oplus$ 表示按位异或运算。

In the first test case, $m = 72 \cdot 1 = 72$ and has $12$ divisors $[1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72]$. The $3 \times 3$ multiplication table looks like that:

1

2

3

1

1

2

3

2

2

4

6

3

3

6

9

For each divisor of $m$ that is present in the table, the position with minimum row index is marked. So the array of answers $a$ is equal to $[1, 1, 1, 2, 2, 0, 3, 0, 0, 0, 0, 0]$. There are only $6$ non-zero values, and xor of $a$ is equal to $2$.

In the second test case, $m = 10 \cdot 15 = 150$ and has $12$ divisors $[1, 2, 3, 5, 6, 10, 15, 25, 30, 50, 75, 150]$. All divisors except $75$ and $150$ are present in the $10 \times 10$ table. Array $a$ $=$ $[1, 1, 1, 1, 1, 1, 3, 5, 3, 5, 0, 0]$. There are $10$ non-zero values, and xor of $a$ is equal to $0$.

In the third test case, $m = 1 \cdot 210 = 210$ and has $16$ divisors $[1, 2, 3, 5, 6, 7, 10, 14, 15, 21, 30, 35, 42, 70, 105, 210]$. The $6 \times 6$ table with marked divisors is shown below:

1

2

3

4

5

6

1

1

2

3

4

5

6

2

2

4

6

8

10

12

3

3

6

9

12

15

18

4

4

8

12

16

20

24

5

5

10

15

20

25

30

6

6

12

18

24

30

36

Array $a$ $=$ $[1, 1, 1, 1, 1, 0, 2, 0, 3, 0, 5, 0, 0, 0, 0, 0]$. There are $8$ non-zero values, and xor of $a$ is equal to $5$.

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

1

2

3

1

1

2

3

2

2

4

6

3

3

6

9

对于 $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$ 乘法表如下所示：

1

2

3

4

5

6

1

1

2

3

4

5

6

2

2

4

6

8

10

12

3

3

6

9

12

15

18

4

4

8

12

16

20

24

5

5

10

15

20

25

30

6

6

12

18

24

30

36

数组 $a = [1, 1, 1, 1, 1, 0, 2, 0, 3, 0, 5, 0, 0, 0, 0, 0]$。其中共有 $8$ 个非零值，且 $a$ 的异或和为 $5$。