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

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

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

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

10290 WA..

Post by Mahbub »

Can any output be >3 ?

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

Thanks!
--------
Mahbub

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel »

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

arc16
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia

Post by 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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

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

Post by 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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry »

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:

Post by 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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

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

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

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

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

Post by 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
Learning poster
Posts: 60
Joined: Tue Aug 13, 2002 2:39 am
Location: Mexico

Having doubts...

Post by Miguel Angel »

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

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

10290

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

Post Reply

Return to “Volume 102 (10200-10299)”