Alice and GCD

4.7

3 votes
Algorithms, Dynamic Programming, Dynamic Programming and Bit Masking, Bitmask
Problem

Alice has been given an array A of N integers where N is even.

In each round Alice can choose any two integers from the array and delete them.

Points Alice will get in each round will be the gcd(num1,num2)round

num1 and num2 are the integers which Alice has chosen and turn is the current round. Alice total score is the sum of scores that Alice has obtained in each round.

Determine the maximum total Score which Alice can get.

Constraints:

1N201A[i]109

Input Format:

The first line contains an integer N which denotes the length of array A.

The second line contains N space separated positive integers, denoting elements of array A

Output Format:
An integer denoting the maximum total score which Alice can achieve

Sample Input
4
3 4 9 5
Sample Output
7
Time Limit: 5
Memory Limit: 256
Source Limit:
Explanation

Round1 : select num1 = 4, num2=5 . gcd(num1,num2)*round = 1*1=1.
Round2 : select num1 = 3, num2=9 . gcd(num1,num2)*round = 3*2=6.
Maximum total score = 6+1 = 7

Editor Image

?