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