## 10302 - Summation of Polynomials

Moderator: Board moderators

mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt

### 10302 - Summation of Polynomials

I get WA with this code...any tips :
[cpp]
#include <iostream.h>
#include <stdio.h>
#include <math.h>

int
num,
i;

float sum;

void main()
{
while (!cin.eof() && cin>>num)
{
sum=0;
for (i=0;i<=num;i++)
sum+=pow(i,3);
printf("%.0lf\n",sum);
}
}
[/cpp]

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:
Clearly, there should be value overflow~

mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt
Well a friend just mentioned that any number type can only be accurate upto some length after which there will be some zeroes inputted automatically. Oh well.

Joe Smith
New poster
Posts: 26
Joined: Wed Apr 17, 2002 5:56 am

### Hint

mido wrote:Well a friend just mentioned that any number type can only be accurate upto some length after which there will be some zeroes inputted automatically. Oh well.
gcc (which is what UVA uses) has a "long long" data type which supports integers up to 2^64. So does Java's "long".

popel
New poster
Posts: 33
Joined: Fri Mar 15, 2002 2:00 am
Contact:

### Formula

1^3 + 2^3 + 3^3 + ... ... ... +n^3

Sn=(n*(n+1)/2)^2

scythe
New poster
Posts: 12
Joined: Mon Oct 07, 2002 12:25 pm

### Formula using the question hints

I worked on the helper formulas given in the task and i came up with the following formula:

Sn = ((N-1)*N*(N+1)*(N+2) + 2*N*(N+1)) / 4
which is actually an uglier form of your formula

I got AC using big numbers.

supermin
New poster
Posts: 37
Joined: Sat Oct 12, 2002 9:54 am
Location: (Taiwan)
Contact:

### Re: Formula using the question hints

I think this question can just use the long double.=>(%Lf)

it can solve it very quickly.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
long long works, and also gets you AC with good time.. =)

mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt

### 10302 again

Anything wrong with this:

[cpp]
#include <iostream.h>
#include <stdio.h>
#include <math.h>

long long
num,
i,j;

long long sum;

void main()
{
while (!cin.eof() && cin>>num && !cin.fail())
{
sum=0;
for (i=0;i<=num;i++)
{
long temp=1;
for (j=0;j<3;j++)
temp*=i;
sum+=temp;
}
cout<<sum<<endl;
}
}

[/cpp]

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
Your program seems to run ok.

But you might consider using a formula for the sum of Nth cube instead of using the iteration:

for (i=0;i<=num;i++)
{
long temp=1;
for (j=0;j<3;j++)
temp*=i;
sum+=temp;
}

the formula is :

(N*(N+1)/2)^2

Chow Wai Chung
New poster
Posts: 21
Joined: Sun Jan 19, 2003 4:01 pm
Location: Hong Kong

### 10302 why WA??

This problem seem very easy, and i use (n*(n+1)/2)^2 to calculate the answer, but i get a WA....

Would anyone tell me what is my mistake??

[c]
#include <stdio.h>
#include <math.h>

int main()
{
long long result,n;
while(scanf("%lld",&n)!=EOF)
{
result=(long long)pow(n*(n+1)/2,2);
printf("%lld\n",result);
}
return 0;
}
[/c]

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:
Your formula looks great and you might want to try x = 50,000 and check your result using calculator. Most likely it is an overflow or precision problem.

-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

IIUC GOLD
New poster
Posts: 19
Joined: Tue Jun 11, 2002 4:27 pm
Contact:
Use the following

result = n * n * (n + 1) * (n + 1) /4;

result=(long long)pow(n*(n+1)/2,2);

Chow Wai Chung
New poster
Posts: 21
Joined: Sun Jan 19, 2003 4:01 pm
Location: Hong Kong
Thank you to turuthok and IIUC GOLD

I solved this problem by using n * n * (n + 1) * (n + 1) /4, may be i lost something when cast the pow() to long long before.

mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt
Got AC long time ago...who would've thought you needed for the temp variable....