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

[..]

........Just because your algorithm is too slow
There are some ways to solve this problem faster.......

[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

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

[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;
}
}

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

[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

Code: Select all

1
1
1
2
2
2
1
1
1
2
45
64
4

[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

[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

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

[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

[helloneo]

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

[x140l31]

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

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