Codeforces Round 972 (Div. 2) |
---|
Finished |
You are given two arrays a1,a2,…,an and b1,b2,…,bn.
You must perform the following operation exactly once:
Find the maximum possible value of gcd(a1,a2,…,an)+gcd(b1,b2,…,bn) 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≤t≤105), 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≤n≤2⋅105), representing the number of integers in each array.
In the next line, you are given n integers a1,a2,…,an (1≤ai≤109) — the elements of the array a.
In the last line, you are given n integers b1,b2,…,bn (1≤bi≤109) — the elements of the array b.
The sum of values of n over all test cases does not exceed 5⋅105.
For each test case, output a line with two integers: the maximum value of gcd(a1,a2,…,an)+gcd(b1,b2,…,bn) after performing the operation exactly once, and the number of ways.
5811 4 16 17 3 24 25 88 10 4 21 17 18 25 2146 4 24 1315 3 1 14213 145 8820 17 15 11 21 10 3 79 9 4 20 14 9 13 1218 1315 20
2 36 3 2 2 3 2 36 6 1
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.
Name |
---|