10958 - How Many Solutions?

[erdos]

Hi,

I'm solving 10958 just by counting the divisors and I think I'm doing it efficiently. (ie: just going to the square root).

I'm getting TLE!
The TLE could be caused by an overflow in the cycle but that's not the case since I'm using long longs for all envolved variables.
Here is the main part:

typedef long long ulong;

ulong labs(ulong n)
{
return n<0 ? -n : n;
}

ulong n, m, p;
ulong i, numerator;
int countDivisors = 0;
if(scanf("%llu %llu %llu", &n, &m, &p)==EOF)
break;
if(n==0||m==0||p==0)
break;
numerator = labs(n*m*p*p);
for(i=1; i*i<=numerator; i++)
{
if(numerator % i == 0)
{
/*one divisor is i, the other if numerator/i*/
if(i*i==numerator)
{
countDivisors++;/*i and numerator/i are the same*/
}
else
{
countDivisors+=2;
}
}
}

I even replaced the && for || and check the end also for EOF just in case and it keeps getting TLE.
Any suggestions?

Jose Carlos

[david]

This seems to be a real TLE.
Since what you have to do is find the number of divisors of a lot of numbers in a limited range, you can do this much faster by precomputing the list of primes in that interval and factoring.

[erdos]

Hi,

Yes you are right.
I just applied the algorithm I did 3 years ago for problem 294 (count divisors) and got AC in 0.021.

I wasn't remembering that way to count the divisors of a number faster.
(I factorize the number and multiply the exponents)
But it seems to be even a faster algorithm since there are 10x faster times. (perhaps using a sieve for the primes before, since I'm not computing the primes).

Thanks,

Jose Carlos