Tip Top Game SPOJ


my code :Ideone Link Click here

getting TLE :

Is there any efficient algorithm to solve this one?
Thanks in advance :slight_smile:

For even a single input of range 10^18, your code makes 10^9 iterations. That alone takes more than a second. And over that you have 10^5 test cases in total. So this certainly doesn’t work. Think of some different approach. For this problem, you need not know what exactly the number of divisors for given input is(You know why and what you needed).

Hint : On a paper, write number of divisors for numbers less than 50 and you will get it :slight_smile:

1 Like

If a number is a perfect square, it has an odd number of divisors. It is isn’t, the number of divisors is even. Divisors of 16 are - 1, 2, 4, 8, 16; while divisors of 27 are - 1, 3, 9, 27. So you need to check if the number is a perfect square. So now your task is to think up an efficient algorithm for that :slight_smile: