1 / 4
Dec 2012

Problem PUCMM2101
Separated from previous thread.

#include<stdio.h>
int main()
{
      int t,n,i;
      scanf("%d",&t);
      while(t>0)
      {
                int s=0;
                scanf("%d",&n);
                for(i=n;i>0;i--)
                {
                                s+=(n-i+1)*i*i*i;
                                if(s>1000000003)
                                s=s%1000000003;
                }
                printf("%d\n",s);
                t--;
      }
      return 0;
}

Pls help!![/quote]

The issue is not the modulo operation. Didn't you check? Your code works fine for test cases 113, 114, 115, ...

You should think about overflow problems. What will your code do for test cases near the upper limit? i*i*i might be a huge number wink

And: it is possible to calculate the result directly, without iterating. You may want to seach the internet for formulas of "Series Sums of the Powers"...

  • created

    Dec '12
  • last reply

    Dec '12
  • 3

    replies

  • 171

    views

  • 2

    users

  • 1

    link

Really !! Sorry to waste your time.. Actually iam new to programming and don't know anything beyond arrays,strings and pointers.
But how to check ??
I mean to say,that how can i calculate the exact value of f(113). I just know the value iam getting from my code, how do i crosscheck?? 1^3+2^3+......113^3 is too long to calculate even with calculator.

So the actual mistake is i didn't considered Overflow Problems . Right ?? Actually I thought a simple logic would solve this problem, thought nothing beyond that.

Hey i have searched on sums of power, but i really can't understand what's different in them.
For eg: In the current problem, the statement should be:

s=( n * n * (n+1) * (n+1) * (n+1) / 4)  -  ( n * (n+1) * (2*n+1) * (3*(n)*(n) + (3*n) - 1)) / 30;

i.e Sum.[ m^3 * (n+1-m) ]
i.e ( (n+1) * Sum.[m^3] ) - Sum.[m^4]
which is huge indeed !!
not even in the range of long long int.
*Sum. stands for Summation.

[quote="aditya_kakarot"]

s=( n * n * (n+1) * (n+1) * (n+1) / 4)  -  ( n * (n+1) * (2*n+1) * (3*(n)*(n) + (3*n) - 1)) / 30;

i.e Sum.[ m^3 * (n+1-m) ]
i.e ( (n+1) * Sum.[m^3] ) - Sum.[m^4]
which is huge indeed !!
not even in the range of long long int.
*Sum. stands for Summation.[/quote]
You are right, these expressions give results which might exceed the range of long long ( I didn't check this.). That's one reason for me to love Python, which is unlimited in the range of integer values smiley
I suppose now it is time to come back to the area of modulo arithmetics. There are rules for modulo operations, like (a+b)%c = (a%c + b%c)%c, which help to avoid overflows.

Suggested Topics

Topic Category Replies Views Activity
C and C++ 0 22 13d

Want to read more? Browse other topics in C and C++ or view latest topics.