Even Odd GCD (Hard Version)
Time Limit: 2.0 s
Memory Limit: 256.0 MB
Description
You are given an array \(A[]\) and the length of the array is N. You need to rearrange array \(A[]\) such way that sum of GCD odd index and even index is as maximum as possible.
Let's see,
Odd index GCD of array \(A[]\), X = GCD \((A_1, A_3, A_5,...A_N)\). (all odd index 1 to N)
Even index GCD of array \(A[]\), Y = GCD \((A_2, A_4, A_6,...A_N)\). (all even index 1 to N)
After rearrange of array \(A[]\), Find Maximum possible sum of X+Y.
GCD means Greatest Common Divisor. For example,
GCD(2,4,6) = 2, that means 2 is the largest possible number which divide all number appear in the set.
Note : The only difference between Easy version and Hard version limit of N and array A[].
Input
T : Number of Test case.
N : Length of the array A[].
A[] : Number of element exactly N.
\(1 <= T <= 5\)
\(2 <= N <= 10^5\)
\(1 <= A[] <= 10^5\)
Output
In each test case, print the maximum sum.
Sample
Input | Output |
---|---|
|
|
First test case:
Information
- ID
- 1077
- Difficulty
- 9
- Category
- Number_Theory Click to Show
- Tags
- # Submissions
- 106
- Accepted
- 6
- Accepted Ratio
- 6%
- Uploaded By
Related
In following contests: