← 返回题目列表

Codeforces · 2005/D

D. 改变 GCD

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

给定两个数组 $$$a_1, a_2, \ldots, a_n$$$ 和 $$$b_1, b_2, \ldots, b_n$$$。

您必须执行以下操作一次:

- 选择任何索引 $$$l$$$ 和 $$$r$$$ 使得 $$$1 \le l \le r \le n$$$;
- 将 $$$a_i$$$ 和 $$$b_i$$$ 交换为所有 $$$i$$$,使得 $$$l \leq i \leq r$$$。

执行一次运算后,求 $$$\text{gcd}(a_1, a_2, \ldots, a_n) + \text{gcd}(b_1, b_2, \ldots, b_n)$$$ 的最大可能值。还找到达到最大值的不同对 $$$(l, r)$$$ 的数量。

输入

在输入的第一行中,您将获得一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$),即测试用例的数量。然后是每个测试用例的描述。

在每个测试用例的第一行,给出一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$),表示每个数组中整数的数量。

在下一行中,您将获得 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 数组 $$$a$$$ 的元素。

在最后一行中,您将获得 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le 10^9$$$) — 数组 $$$b$$$ 的元素。

所有测试用例的 $$$n$$$ 值的总和不超过 $$$5 \cdot 10^5$$$。

输出

对于每个测试用例,输出一行包含两个整数:执行一次操作后 $$$\text{gcd}(a_1, a_2, \ldots, a_n) + \text{gcd}(b_1, b_2, \ldots, b_n)$$$ 的最大值,以及方式数。

示例

输入 #1

5
8
11 4 16 17 3 24 25 8
8 10 4 21 17 18 25 21
4
6 4 24 13
15 3 1 14
2
13 14
5 8
8
20 17 15 11 21 10 3 7
9 9 4 20 14 9 13 1
2
18 13
15 20

输出 #1

2 36
3 2
2 3
2 36
6 1

注意

在第一个、第三个和第四个测试用例中,没有办法在任何数组中实现比 $$$1$$$ 更高的 GCD,因此答案是 $$$1 + 1 = 2$$$。任何一对 $$$(l, r)$$$ 都会获得相同的结果;例如,在第一个测试用例中,有 $$$36$$$ 这样的对。

在最后一个测试用例中,您必须选择 $$$l = 1$$$, $$$r = 2$$$ 才能最大化答案。在本例中,第一个数组的 GCD 为 $$$5$$$,第二个数组的 GCD 为 $$$1$$$,因此答案为 $$$5 + 1 = 6$$$,路数为 $$$1$$$。