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

## 10958 - How Many Solutions?

**Moderator:** Board moderators

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

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

Jose Santos

http://ctp.di.fct.unl.pt/~jcas

http://ctp.di.fct.unl.pt/~jcas