10958 - How Many Solutions?

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

erdos
New poster
Posts: 32
Joined: Sat Jul 06, 2002 9:38 pm
Location: Lisbon
Contact:

10958 - How Many Solutions?

Post by 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
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm

Post by 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
New poster
Posts: 32
Joined: Sat Jul 06, 2002 9:38 pm
Location: Lisbon
Contact:

Post by 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

Post Reply

Return to “Volume 109 (10900-10999)”