Yesterday I found interesting solution for 850B - Arpa and a list of numbers.

Let G=gcd of all numbers after all operations.
First observation was if I have some prime number p which divides G, then I can easy in O(number of different numbers in array a) calculate minimum cost to make list good. Now question is only for which prime numbers I will calculate minimum cost.

I have some MAGIC constant and I will calculate minimum cost for first MAGIC prime numbers and MAGIC most frequent prime numbers which are not in first MAGIC primes. Frequency of some p is increased by 1 if p divides a[i].

First idea was to set MAGIC=12, this will pass all official test data, but there is counter-example. We can choose some prime P which is not in first 12 primes and put in array a numbers: P, 2P-1, 2P-1, 4P-1, 4P-1, 6P-1, 6P-1, ... and so on while numbers are less than 10^6.

But there is way how to avoid this problem. We can see that numbers in array in that example grow very fast so N will be small and that means that we can calculate minimum cost for more primes, so if I set
MAGIC=min(3*10^7/number_of_different_numbers_in_array, number_of_primes_less_than_10^6)
then algorithm will work on that example.

Is there any counter-example for this algorithm and if counter-example doesn't exist, why is that?
Here is my solution: 30086367