10290 - {Sum+=i++} to Reach N

[Caesum]

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.

[Mahbub]

Can any output be >3 ?

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

Thanks!
--------
Mahbub

[Adrian Kuegel]

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

[arc16]

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

[Adrian Kuegel]

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.

[arc16]

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++)

[Larry]

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

[Dominik Michniewski]

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

[Adrian Kuegel]

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

[Dominik Michniewski]

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

[Dominik Michniewski]

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

Code: Select all

cut it off ...

Dominik

[Dominik Michniewski]

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

Dominik

[Dominik Michniewski]

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

Thanks all for help )

Dominik

[Miguel Angel]

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

[hank]

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]