TIPTOP Spoj

Logic : 

           First of all we will try to solve problem using brute force solution.

           

           For Given N find all divisors count them and if count is Odd then answer will be 

           ''Yes"  otherwise "No".

           So finding divisors of a number can take Sqrt(N) time and N can be 10^18 that mean

           time complexity will be O(T*sqrt(N)) which will fail and give time limit exceeded.

           

           Now we will write number of divisors from N = 1 to 50 and then find some pattern.

           (Why 50 well you can take 1000 :P it depend on you)

           

            

     1, 2, 2, 3, 2, 4, 2, 4, 3, 4, 2, 6, 2, 4, 4, 5, 2, 6, 2, 6, 4, 4, 2, 8, 3, 4, 4, 6, 2, 8, 2, 6, 4, 4, 4, 9, 2, 4, 4, 8, 2, 8, 2, 6, 6, 4, 2, 10, 3, 6

      now list all number N where count of divisors are odd(Why? Odd well there are so many even numbers so try to find relation from small set)

          N = 1 , count 1

          N = 4,  count 3

          N = 9,  count 3

          N = 16, count 5

          

           I think thats enough to find a relation or pattern , so by looking at N we can say that if count of divisors are odd then that number must be a perfect square number. 

          

           Now our problem reduced to detect that given number is perfect square number or not

           we can apply a standard method for this one which is binary search and also we can try some hack ;) 

          so here we will see only hack approach you can read about binary search and easily apply.

  

        Hack Approach :

              Suppose given number is N , find square root of N which is built in almost all programming languages.

              SQRT_OF_N = sqrt(N)  
              now we knew that if N is perfect square then if we multiply its square root we can get N again otherwise we will get smaller number than N. :D

Below you can see solution (both approaches)

#include <iostream>

#include <sstream>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <cctype>

#include <string>

#include <vector>

#include <list>

#include <set>

#include <map>

#include <queue>

#include <stack>

#include <algorithm>

#include <functional>

using namespace std; 

#define DEBUG(x) cout << '>' << #x << ':' << x << endl;

#define REP(i,n) for(int i=0;i<(n);i++)

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)

#define FORD(i,a,b) for(int i=(a);i>=(b);i--)

inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }

const int INF = 1<<29;

typedef long long ll;

inline int two(int n) { return 1 << n; }

inline int test(int n, int b) { return (n>>b)&1; }

inline void set_bit(int & n, int b) { n |= two(b); }

inline void unset_bit(int & n, int b) { n &= ~two(b); }

inline int last_bit(int n) { return n & (-n); }

inline int ones(int n) { int res = 0; while(n && ++res) n-=n&(-n); return res; }

template<class T> void chmax(T & a, const T & b) { a = max(a, b); }

template<class T> void chmin(T & a, const T & b) { a = min(a, b); }

/////////////////////////////////////////////////////////////////////

bool SQRT(long long x) {

double sq = sqrt(x);

long long sq_l = sq;

if(sq_l * sq_l == x) return true;

return false;

}

bool BS(long long x) {

long long low = 1;

long long high = 1e9;

while(high - low >= 2) {

long long mid = (low + high) >> 1;

if(mid * mid >= x) {

high = mid;

} else {

low = mid;

}

}

for(long long i = low; i <= high; ++i) {

if(i*i == x) return true;

}

return false;

}

int main()

{

int T;

scanf("%d", &T);

int t = 1;

while(T--) {

long long N;

scanf("%lld", &N);

printf("Case %d: ", t++);

if(BS(N)) {

puts("Yes");

} else {

puts("No");

}

}

    return 0;

}

Happy Coding :)