10290  {Sum+=i++} to Reach N
Moderator: Board moderators
10290  {Sum+=i++} to Reach N
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.
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.
10290 WA..
Can any output be >3 ?
If it can..plz give me some examples..or any clue about the solutuin..
Thanks!

Mahbub
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
I think this link will help you:
http://mathpages.com/home/kmath107.htm
http://mathpages.com/home/kmath107.htm

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

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

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:

 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 ...
Dominik
Maybe in this function I made mistake ? But I think that it's correct ...
Code: Select all
cut it off ...
Last edited by Dominik Michniewski on Fri Oct 11, 2002 11:49 am, edited 1 time in total.

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:

 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
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]
[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]