OJ Board

People keep emailing me about this, so here is my advice and I will ignore any more emails:
You do not actually need to factorise the number completely in order to work out the answer. When you have gone so far you have three choices: the remainder is prime, it is a square or it is the product of two factors.

Can any output be >3 ?

If it can..plz give me some examples..or any clue about the solutuin..

Thanks!
--------
Mahbub

I think this link will help you:
http://mathpages.com/home/kmath107.htm

hi adrian,
if i understand correctly from the url you mentioned, the answer is just the number of odd factor of the input. Is it right?
what if input is 0? is the output 1?
thank you

Yes, the answer is the number of odd divisors. I don't think that there is a 0 in the input, I would print 1.

so now i only have to find how to handle those e14 input in pascal...
i have tried int64, cardinal, qword, etc (from FPC), but i keep geting compile error. Anyone know the reason ? (before i switch to c++)

So how do we optimize this? I can't it from not going to TLE..

My algorithm is done in such way:

1. compute primes in range 1..1,5*10^7
2. for each input value:
2.0. remove 2^N factor from given value
2.1. generate prime factorization
2.2. number of divisors = (p1+1)*(p2+1)....*(pn+1) where pi are exponent of prime factors in factorization
2.3. output number of divisors

but judge says, that program got WA (after 50 secs...) Is there way wrong? why? Could anyone tell me other way to compute number of odd divisors in this case ?

Dominik

Why do you calculate only up to 1,5*10^7? I calculated all primes up to 3*10^7. That is sqrt(9e14).

yes, you have right
but I only must consider odd numbers ...
and I have table only for numbers like 2*i+1, where i is index in table ... is it not enough ?

Dominik

Function, which generates primes to table PRIM, is placed below :
Maybe in this function I made mistake ? But I think that it's correct ...
Dominik

And I forgot ....
Table has 15000005 elements, but store numbers up to 30000011, which is more than root of 9e14 ....

Dominik

Finally I got accepted )) with 32 sec time ))
I miss one thing in counting )) very stupid mistake in myalgorithm ...

Thanks all for help )

Dominik

I know it can speed up the problem by using a table with primes, but can be another way?

My method is:
[cpp]
#include <iostream>
using namespace std;
void main()
{
register long long int n=0,front=0,tail=0,s=0,t=0,ans=0;
while( cin>>n ){
s=0; front=1; tail=1; ans=0; t=n/2;
while( front<=t ){
if(s<n){
s+=tail;
tail++;
}else if(s>n){
s-=front;
front++;
}else{
ans++;
s+=tail;
tail++;
}
}/*while*/
cout<<ans+1<<endl;
}
}

[/cpp]

My method is simple but I always get TLE.
What's wrong in my code?[/cpp][/c]