Problem Link: Spoj problem
Code: https://ideone.com/2afY09
Approach: finding all the possible prime factors of the 1st number, and storing them in a map(map1) and for subsequent numbers inserting them into another map(map2) and then later comparing them to map1 if map2 doesn’t have map1 values than it cannot be in a gcd while if they are present then minimum of map1 and map2 values.
For example (sample input):
3
4 1 2 3 4
1 36
2 6 5
after 1st iteration:
map1 2 = 3
map1[3] = 1
after 2nd iteration:
map1 2 = 2
map1[3] = 1
after 3rd iteration:
map1 2 = 1
map1[3] = 1
and multiplying them in the last. pow(2,1)*pow(3,1) = 6 (answer)
Result: TLE
How can I optimize my code or please suggest a better algorithm to solve this problem?
Thanks in advance!