Little Elephant and Divisors | CodeChef

Number of test cases is 10^5.
For each test case, N can be as large as 10^5. So for each test case time complexity would be atleast O(N) as we will have to take the input.
Total time complexity would be O(N*t)=O{10^10)
Is it possible to solve the question with runtime 2sec??

The sum of values of N in each test file does not exceed 100000

I have used prime sieve to calculate prime numbers till 10^5 and stored it in a array in ascending order.
then for each test case, calculated the gcd for the input and checked for the smallest prime that divide this gcd.
Isn’t it a good approach?

Consider the test case


This test case would absolutely kill your code because there are \pi(max(A))=O(\frac{max(A)}{\log(max(A))}) primes, and T test cases. So your time complexity is
O(T\pi(max(A)) + \sum Nlog(max(A)) + max(A)\log(\log(max(A))))
Which won’t pass the constraints.
First term is iterating through all primes, second term is calculating GCD, and third term is sieve.
If you can’t figure out how to solve it, you can read my answer.

How to solve it

Use a set instead of a vector, And check whether res is a prime using the
prime.count(res) It will return 1 if res is a prime. Then output res directly. If it’s not, then iterate through all elements in the set.
This is faster because a composite number x has at least one prime less that \sqrt{x}.
Your new time complexity is
O(T\pi(\sqrt{max(A)}) + \sum Nlog(max(A)) + max(A)\log(\log(max(A)))log(max(A)))
Which will pass
CodeChef: Practical coding for everyone

got it. Thank you :slight_smile: :upside_down_face:

Can you help me understand the syntax you used while iterating through elements in the set??
for(auto &ans : prime)

That’s just syntax, there’s not much to explain.

auto -use whatever datatype the set contains

& - don’t create an extra copy of the value.
Do NOT put this if you’re going to change the value.

ans - what name you want the variable to have

: - you can read this as “In”, so : prime becomes in set prime.