Find the next multiple of N that is a perfect square number Given a number \$t\$, (\$1 \leq t \leq 1000\$) that represent
  testcases and \$t\$ numbers \$n\$ (\$1 \leq n \leq 10^9\$). Show the
  next multiple of \$n\$ that is a perfect square number.
  
  Example of input:

5   
5 9 10 12 13

  
  Example of output:

Case #1: 25
Case #2: 9
Case #3: 100
Case #4: 36
Case #5: 169



My solution iterates over all the next perfect squares of \$n\$ (using this formula \$ \left(\lfloor \sqrt{x} \rfloor + 1\right) ^ 2 \$ until it's a multiple of \$n\$.



#include &lt;stdio.h&gt;
#include &lt;string.h&gt;
#include &lt;math.h&gt;

unsigned long long myPow(unsigned long long x){
    return x*x;
}

int main(){

    unsigned int j;

    unsigned int t;
    scanf("%u",&amp;t);

    for(j = 1; j &lt;= t; j++){
        unsigned long long n;
        scanf("%llu",&amp;n);
        double sqrtn = sqrt(n);
        if(sqrtn == (unsigned long long) sqrtn) //test if N is a perfect square
            printf("Case #%d: %llu\n",j,n);
        else{
            unsigned long long i = n;
            while((i = myPow(floor(sqrt(i))+1)) % n != 0);//find the next perfect square multipe of n
            printf("Case #%d: %llu\n",j,i);
        }
    }
}


This solution encounters "Time limit exceeded". Is there a faster way of finding the solution?
I'm afraid we need to use… math.

Take any square number and look at its prime factorization. For example, \$ 100 = 2^2·5^2 \$; \$ 144 = 2^4·3^2 \$; \$ 729 = 3^6 \$. The thing that's common to all of these examples is that the exponent of each prime in the factorization is even. And that's because if you take any number \$ n \$, with factorization $$ n = 2^a·3^b·5^c\dotsm $$ then its square is $$ n^2 = 2^{2a}·3^{2b}·5^{2c}\dotsm $$ where all the exponent are even.

So if you want to find the smallest multiple of \$ m \$ that's a square, then you can factorize $$ m = 2^a·3^b·5^c\dotsm $$ find the odd exponents among \$ a, b, c, \dotsc \$, and then multiply by the appropriate primes to make all the exponents even.

Let's take the number \$ 12 \$ as an example. First, factorize \$ 12 = 2^2·3^1 \$. Then note that \$ 3 \$ is raised to an odd exponent in the factorization. So we need to multiply by \$ 3 \$ to get \$ 2^2·3^2 = 36 \$ which is \$ 6^2 \$.

A bigger example: \$ 24696 \$. First, factorize \$ 24696 = 2^3·3^2·7^3 \$. Then note that both \$ 2 \$ and \$ 7 \$ are raised to odd exponents in the factorization. So we need to multiply by \$ 2·7 \$ to get \$ 2^4·3^2·7^4 = 345744 \$ which is \$ 588^2 \$.