Sum of mathematical series with Mod 10^9+7

[abdalimran]

Problem link: http://www.lightoj.com/practice_contest_showproblem.php?contest_id=552&problem=E

You are given a mathematical series

1^3+2^3+3^3+4^3………………………..N^3

You are given the value of N output the sum with Mod 10^9+7

Input:

Input start with an integer T(T≤10000).

Each test case contain a integer N (1≤N≤10^9)

Output

For each test case, print the case no and the Sum of series. Mod 10^9+7

I've written the following code for this:

#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

int main()
{
    int t;
    const int m=1000000007;

    scanf("%d",&t);

    for(int i=1; i<=t; i++)
    {
        unsigned long int n;
        int ans;
        int sum=0;

        scanf("%ld",&n);

        sum=(((n%m)*(n%m))*(((n%m)+1)*((n%m)+1)))/4;

        printf("Case %d: %d\n",i,sum);
    }

    return 0;
}

I am getting WA...why? How to solve it?

[MiiNiPaa]

why?

Integer overflow probably. int is very likely to have 4 bytes in size. So maximum value you can store there is 2 147 483 647. Which is not enough in case of large N.

Also n%m does not do anything as in assigment is stated that n is always less than m.
You probably need to wrap around sum, not n.

[dhayden]

There are two things you have to deal with here: the overflow and the division by 4 at the end. Consider the largest case: N=1,000,000,006. You can't multiply N*N in a 32 bit number, so you'll need a 64 bit value for that (probably an unsigned long long). But even there, if you multiply N*N*(N+1)*(N+1), that result won't fit in 64 bits either, so you need to use the property

(a*b) mod c == (a mod c)*(b mod c) mod c

. In other words, take the modulo after each multiplication.

That handles the multiplication but what about the division by 4? I don't think that you can simply take the result and divide by 4. Instead, consider the factors: N*N*(N+1)*(N+1). Either N is even or N+1 is even. So N*(N+1) is guaranteed to be even and that means you can divide it by 2. So lets rearrange the terms to be (N*(N+1)/2) * (N*(N+1)/2) = (N*(N+1)/2)^2.

Now it's real easy, but I'll let you do the final bit of code. Just remember:
- use unsigned long long for the multiplication.
- Take the modulo after each term, and again with the result.