Array and operations : Codeforces Round 284

algorithm
prime-factor

#1

Problem : link text

I began by first prime-factorizing each number of the array. Given one good-pair (ik,jk) we can divide both numbers A[ik] and A[jk] by their common prime powers i.e if A[ik]=2^5 * 3^4 and A[jk]=2^3 * 3^7 then we can divid both of them by 2 a total of 3 times and divide by 3 a total number of 4 times. The number of operations increase by the minimum of the common prime powers i.e by 7.

Total number of operations can then be taken as the sum over all common prime powers for all good pair given.
Here is my approach.

My code : link text

Pretest 5 contains this test data. My answer on this is 28 but the correct answer is 31.

Can anyone explain why the output is 31 and the correct approach to solve the problem?

10 9

67108864 8 2 131072 268435456 256 16384 128 8 128

4 9

5 10

6 9

9 10

1 4

3 8

8 9

1 2

4 5


#2

editorials :- codeforces go through it


#3

The problem is that you are doing is greedily, which is wrong approach.
Try this test case :

4 3
8 4 32 8
1 2
2 3
1 4

Your code is giving 3 as output, while the correct output should be 5.

If we change the order of the input it gives correct answer.

Hope it helps!!

Happy Coding!!!


#4

Read that. Could not completely understand it.
Hence asked here.