Doubt: ADAGCD(Ada and GCD) on Spoj

general
1

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!

1 Like
2

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 ++){
    if(!lp[i]){
        for(int j = i; j < 10000001; j += i)
            lp[j] = i;
    }
}
3

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

4

Hey @therisingsun

My implementation uses a sieve to find the factors. Can you tell me why it’s still TLE?

Code: https://ideone.com/IHo1jt