CF2005D Alter the GCD

You are given two arrays $ a_1, a_2, \ldots, a_n $ and $ b_1, b_2, \ldots, b_n $ . You must perform the following operation exactly once: - choose any indices $ l $ and $ r $ such that $ 1 \le l \le r \le n $ ; - swap $ a_i $ and $ b_i $ for all $ i $ such that $ l \leq i \leq r $ . Find the maximum possible value of $ \text{gcd}(a_1, a_2, \ldots, a_n) + \text{gcd}(b_1, b_2, \ldots, b_n) $ after performing the operation exactly once. Also find the number of distinct pairs $ (l, r) $ which achieve the maximum value.

In the first line of the input, you are given a single integer $ t $ ( $ 1 \le t \le 10^5 $ ), the number of test cases. Then the description of each test case follows. In the first line of each test case, you are given a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ), representing the number of integers in each array. In the next line, you are given $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^9 $ ) — the elements of the array $ a $ . In the last line, you are given $ n $ integers $ b_1, b_2, \ldots, b_n $ ( $ 1 \le b_i \le 10^9 $ ) — the elements of the array $ b $ . The sum of values of $ n $ over all test cases does not exceed $ 5 \cdot 10^5 $ .

For each test case, output a line with two integers: the maximum value of $ \text{gcd}(a_1, a_2, \ldots, a_n) + \text{gcd}(b_1, b_2, \ldots, b_n) $ after performing the operation exactly once, and the number of ways.

In the first, third, and fourth test cases, there's no way to achieve a higher GCD than $ 1 $ in any of the arrays, so the answer is $ 1 + 1 = 2 $ . Any pair $ (l, r) $ achieves the same result; for example, in the first test case there are $ 36 $ such pairs. In the last test case, you must choose $ l = 1 $ , $ r = 2 $ to maximize the answer. In this case, the GCD of the first array is $ 5 $ , and the GCD of the second array is $ 1 $ , so the answer is $ 5 + 1 = 6 $ , and the number of ways is $ 1 $ .