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 <stdio.h>
#include <string.h>
#include <math.h>
unsigned long long myPow(unsigned long long x){
return x*x;
}
int main(){
unsigned int j;
unsigned int t;
scanf("%u",&t);
for(j = 1; j <= t; j++){
unsigned long long n;
scanf("%llu",&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?