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

Moderator: Board moderators

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

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

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
New poster
Posts: 26
Joined: Thu Aug 08, 2002 8:04 am

### 10290 WA..

Can any output be >3 ?

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

Thanks!
--------
Mahbub

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
http://mathpages.com/home/kmath107.htm

arc16
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia
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

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia
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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
So how do we optimize this? I can't it from not going to TLE..

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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
Last edited by Dominik Michniewski on Fri Oct 11, 2002 11:49 am, edited 1 time in total.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
And I forgot ....
Table has 15000005 elements, but store numbers up to 30000011, which is more than root of 9e14 ....

Dominik

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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
Learning poster
Posts: 60
Joined: Tue Aug 13, 2002 2:39 am
Location: Mexico

### Having doubts...

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

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

### 10290

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]