Page 2 of 2
Posted: Fri May 16, 2003 8:42 am
by ..
........Just because your algorithm is too slow
There are some ways to solve this problem faster.......
10290 :: Help !!
Posted: Fri Jun 13, 2003 6:24 am
by tep
Please help I got Time Limit Exceeded.. for this problem..
can someone please explain me a good algorithm...
this is how i try to solve this problem
for example n = 9
i can try solving like this :
nWay = number of Ways
p = 9 (integer) ---> inc(nWay)
p + (p+1) = 9
2p + 1 = 9
p = 4 (integer) ---> inc(nWay)
p + (p+1) + (p+2) = 9
3p + (1+2) = 9
p = 2 (integer) ---> inc(nWay)
....
i can denote the problem like this
i am searching for k so that p is integer
k*p + (k-1)*k/2 = n
k*p = n - (k-1)*k/2
p = ( n - (k-1)*k/2 ) / k.......(1)
from equation (1) i conclude that k <= sqrt(2*n)
so i run through the loop k from 1 to <= sqrt(2*n)
pseudo :
for k = 1 to sqrt(2*n)
p = ( n - (k-1)*k/2 ) / k
if p is integer then nWay++
but I got time limit exceeded...
I got clue from
http://mathpages.com/home/kmath107.htm
that but It's also slow.. because I have to search the odd divisor
by running from 1 to sqrt(N)
please help
thanx
Posted: Thu Oct 16, 2003 9:36 am
by anupam
Code: Select all
#include<stdio.h>
#include<math.h>
#define N 30000011
main()
{
long long int i,j,a[N],b,c[N],ans,d;
for(i=2;i<N;i++) a[i]=0;a[0]=a[1]=1;
for(i=2;i<=N/2;i++)
if(!a[i])
for(j=2;i*j<N;j++) a[i*j]=1;
while(scanf("%lld",&d)!=EOF)
{
if(d==0) {printf("1\n");continue;}
while(d%2==0) d/=2;
b=sqrt(d);
for(i=0;i<=b;i++) c[i]=0;
for(i=2;i<=b;i++) if(!a[i] && (d%i)==0)
{c[i]++;d/=i;i=1;}
if(!a[d]) c[1]++;
ans=1;
for(i=1;i<=b;i+=2) ans*=(c[i]+1);
printf("%lld\n",ans);
}
return 0;
}
hello all, why rte?? i used the same limit as you used.
please help.[/i][/b]
10290 Gives T L E.
Posted: Wed Sep 29, 2004 9:55 am
by efr_shovo
10290 gives T.L.E. How Can I solve this problem?Please Help me Some one.
#include<stdio.h>
#include<math.h>
double n,i,j,s,t=1,m;
void main()
{
while(1==scanf("%lf",&n))
{
if(n>0)
{
m=floor(n/2+1);
for(i=0;i<m;i++)
{
s=0;
for(j=i;j<=m;j++)
{
s=s+j;
if(s==n)
t++;
else if(s>n)
break;
}
}
}
printf("%.0lf\n",t);
t=1;
}
}
Posted: Wed Jul 27, 2005 6:06 pm
by I LIKE GN
what is floating point exception...
wht should i do???
i use seive3(bit wise seive function) and only one long double is used
help...
Posted: Fri Aug 19, 2005 9:18 am
by Nazmul Quader Zinnuree
there are less than 1857900 primes <= sqrt(9E14)
And try the following inputs
Code: Select all
0
1
2
3
5
7
4
16
2147483648
11
900000000000000
444444444444444
235642
output should be
Posted: Mon Sep 10, 2007 11:20 am
by lena
it states in the problem ,that the running time will be 100seconds,but why i run only 3seconds ,and get a TLE??
10290
Time Limit: 100 seconds
Memory Limit: 32 MB
5909689 {Sum+=i++} to Reach N Time limit exceeded C++ 3000 2007-09-10 09:13:21
Posted: Mon Sep 10, 2007 1:40 pm
by lena
another code got AC over 3000ms... I got TLE in 3000ms.
20 5520422 Andrzej Kukier 3455 2004 C++ 2007-04-20 23:08:32
Posted: Wed Sep 12, 2007 4:32 pm
by lena
I submit a code which got AC before, and now get a TLE...
I am sure that there are some mistake in the judge.
Re: 10290 - {sum+=i++} to Reach N
Posted: Tue Sep 09, 2008 10:13 pm
by x140l31
I need some help for this problem.
I don't know how to calculate the number of odd divisors of a number efficiently...
Any hint please?
It's possible to calculate it, if I have the prime divisors of it?
thanks
Re: 10290 - {sum+=i++} to Reach N
Posted: Wed Sep 10, 2008 10:42 am
by helloneo
x140l31 wrote:I need some help for this problem.
I don't know how to calculate the number of odd divisors of a number efficiently...
Any hint please?
It's possible to calculate it, if I have the prime divisors of it?
thanks
If N = 2^a * p1^b * p2^c * p3^d ..., the number of odd divisors of N would be (b+1) * (c+1) * (d+1) * ..., where p1, p2, p3, ... are primes other than 2
Re: 10290 - {sum+=i++} to Reach N
Posted: Thu Sep 11, 2008 12:25 am
by x140l31
helloneo wrote:
If N = 2^a * p1^b * p2^c * p3^d ..., the number of odd divisors of N would be (b+1) * (c+1) * (d+1) * ..., where p1, p2, p3, ... are primes other than 2
ohh thanks! i will try it
EDIT::
I get always WA!!
Code: Select all
#include <iostream>
#include <vector>
using namespace std;
typedef vector<int> VI;
int oddDivisors(const VI &p, long long int n)
{
if (n < 3) return 1;
while (n%2 == 0) n /= 2;
int div = 1, res = 1;
while (n > 1 and div < p.size())
{
int x = 1, d = p[div];
while (n%d == 0) { ++x; n /= d; }
res *= x;
++div;
}
if (n > 1) ++res;
return res;
}
int main()
{
VI isPrim(30000000, 1), prim(1, 2);
for (int i = 3; i < 30000000; i += 2)
{
if (isPrim[i])
{
prim.push_back(i);
int incr = i + i;
int aux = i + incr;
while (aux < 30000000) { isPrim[aux] = 0; aux += incr; }
}
}
long long int n;
while (scanf("%lld", &n) == 1) printf("%d\n", oddDivisors(prim, n));
}
why??????????????
Re: 10290 - {sum+=i++} to Reach N
Posted: Thu Feb 03, 2011 1:11 am
by Solaris
I used sieve for generating primes upto sqrt(9e14) (only this takes around 0.9 secs)
Then I calculate number of odd divisors for each given number.
The total time it took was more than 2 secs. I see a lot of people got it AC in < 0.5 secs. Is there any better way of solving this?