Doubt: ADAGCD(Ada and GCD) on Spoj

Problem Link: Spoj problem


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):


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!

1 Like

Hey @sandeep_007

The step that you can optimize to avoid TLE is to find the factors of the number. For finding the factors you are iterating till sqrt(a) and incrementing the loop by 2. You can do some precomputation here to optimize the step of finding all the factors.

Hint for some optimization:

Click to view

You can use sieve of eratosthenes to find the lowest prime factor of every number and then using that lowest prime number you can find all the factors in a much optimized way.(By dividing the number with the lowest prime and then diving the obtained number with the lowest prime factor for that obtained number)

for(int i = 2; i < 10000001; i ++){
        for(int j = i; j < 10000001; j += i)
            lp[j] = i;

Quite good on your part to explain your approach. (y)