I have to try many times before i solve it.
Now i've got AC 0.001, 246 KB, what I think is a really good job.
It is an easy task but you have to know that if you divide by numbers you should divide only to sqrt;-)

Thanks. I had forgot, that I must divide only to sqrt :)
I had TL3)
AC now.

Edited by author 10.12.2010 01:30

I just counted primes in the factorization of the b/a number. O(sqrt(b/a)), but 0.015 sec. Is a human able to do an AC in 0.001 sec using C language? Even if I got 0.015 sec on the such stupid problems like #1409 and #1000!!