SPOJ 16033. Tip Top Game (TIPTOP)

http://www.spoj.com/problems/TIPTOP/
(A little misunderstanding regarding the task, the thing which we need to check is whether the number has even number of divisors or no).
  Judging from the input (10^5 test cases and each texst casu up to 10^18) we can assume that this task is a type where we need to input the number and ouput the answer without much operations. For solving tasks like this I recommend writing a brute force code, output the answer for some number and then spot the pattern easily. You can download the output for the first 1000 numbers below and you might figure out the pattern.

   Download output for first 1000 numbers

  Basically, the answer is yes when the number of divisors is odd. So when the number of divisors of a number is odd? By observing the output you will figure out that it is true when the number is a perfect square. So, let's discuss why is it true.  In case of all prime numbers which can't be perfect squares , the number of divisors is even (only 2 divisors). 

Let us have a list of out divisors of a certain prime numner P.

1 and P

So, when we multiply this number with any other number not equal to himself, we will get a new list of numbers. Supose we multiply with. K

we get, 1, K, P, P*k which is again even. It will turn odd only if there is a number in that list which we wrote 2 times which is K and P so we must multiply a prime number with itself to get a number with odd number of divisors =>only perfect squares have that feature. 

       DOWNLOAD THE FULL SOURCE CODE