Arrayman

Limits 1s, 512 MB

Arrayman is a very famous person. He has an array of n integers. He wants to divide it in a number of subarrays. The cost to create a subarray is the sum of the unique numbers in that subarray. He has to spend sum of unique numbers in each subarray for this. For example: If the array is (2,4,4,6) and he decides to divide like this: {2}, {4,4,6} then total cost will be 2+4+6=12 Taka. But if he divides like this: {2,4},{4,6} then total cost will be 2+4+4+6=16 Taka. Arrayman can divide the array in any number of possible subarrays he wishes (he also can leave the array as it is). But he has to follow one condition. GCD of each subarray must be greater than 1. For example {2,4,6} can be a subarray. But he can’t take {2,4,3} as it’s gcd is 1. In this problem, you need to find the minimum amount of money Arrayman has to spend.


This is a companion discussion topic for the original entry at https://toph.co/p/arrayman