CF2005D.Alter the GCD

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

你必须恰好执行一次如下操作：

• 选择任意下标 $l$ 和 $r$，满足 $1 \le l \le r \le n$；
• 对所有满足 $l \leq i \leq r$ 的 $i$，交换 $a_i$ 和 $b_i$。

请你在恰好执行一次操作后，求 $\gcd(a_1, a_2, \ldots, a_n) + \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$。

对于每个测试用例，输出一行两个整数，分别表示在恰好执行一次操作后，$\gcd(a_1, a_2, \ldots, a_n) + \gcd(b_1, b_2, \ldots, b_n)$ 的最大值，以及达到最大值的 $(l, r)$ 对的数量。

在第 1、3、4 个测试用例中，无法使任一数组的最大公约数大于 $1$，因此答案为 $1 + 1 = 2$。任意一组 $(l, r)$ 都能达到相同的结果，例如在第 1 个测试用例中共有 $36$ 组这样的 $(l, r)$。

在最后一个测试用例中，必须选择 $l = 1$，$r = 2$ 才能使答案最大，此时第一个数组的最大公约数为 $5$，第二个数组的最大公约数为 $1$，因此答案为 $5 + 1 = 6$，且方案数为 $1$。

由 ChatGPT 4.1 翻译