0

I am trying to write a code for sum of square of natural numbers but with mod it's giving wrong answer. What would be the correct way here?

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007

int main()
{
    int N;
    cin>>N;
    cout<< (((N) * (N+1) * (2*N+1))/6)%mod;

    return 0;
}
Sumit Jaiswal
  • 216
  • 1
  • 4
  • 17
  • 2
    Note: your formula corresponds to the sum of the squares of the natural numbers. – Damien Nov 19 '21 at 10:29
  • @Ronald `(N) * (N+1) * (2*N+1)` is (when working with natural numbers, without overflow) always divisible by 6. – harold Nov 19 '21 at 10:37
  • Thanks for pointing out @Damien i have made the change in question. Also, I would like to point out that N is a big number typically in the long long range. I was asked to calculate the sum and return it in `int` return format after doing modulo. – Sumit Jaiswal Nov 19 '21 at 10:45
  • @harold I don't know what made me think that the expression isn't divisible by 6, but you are right. I apologize for the false alert – Ronald Nov 19 '21 at 10:45
  • 1
    Related: [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) – Stef Nov 19 '21 at 11:23
  • @Stef Not related but sure i know why we should not use ``, but in terms of competitive programming, it's a great thing to have. – Sumit Jaiswal Nov 19 '21 at 11:26

1 Answers1

6

(N) * (N+1) * (2*N+1) can be, even if N is less than 1000000007, too large. Namely up to 2000000039000000253000000546, which is an 91-bit number. It is not likely that int on your system is capable of containing such large numbers.

As usual with this type of question, the work-around is a combination of:

  • Using a larger integer type for intermediate products, and
  • Applying modulo reduction on intermediate products, not only at the end.

Using just one of them is not sufficient.

As a consequence of applying modulo reduction earlier, the division by 6 will not work with a normal division, it will have to be a multiplication by the modular multiplicative inverse of 6 mod 1000000007, which is 166666668.

Example code:

mod_mul(mod_mul(mod_mul(N, N + 1, mod), mod_mul(2, N, mod) + 1, mod), inv6, mod)

Using some suitable definition of mod_mul, which can avoid overflow by using long long or a similar type.

harold
  • 61,398
  • 6
  • 86
  • 164
  • Don't we need mod on N and N+1 as well? like `N%mod` and `(N+1)%mod`. N is large enough to go over any data type range when multiplied with itself – Sumit Jaiswal Nov 19 '21 at 10:55
  • @SumitJaiswal you can do that, but it seems like overkill to me. `mod_mul` should be able to handle numbers slightly above `mod` as well, as long as they fit in an `int`. If `N+1` could overflow an `int`, that would be an issue that could be avoided by applying `N %= mod`. – harold Nov 19 '21 at 10:59
  • I guess i was missing that `inv6` for multplication instead of division, and also didn't think about `2*N` it can overflow as well thanx for the help. – Sumit Jaiswal Nov 19 '21 at 11:02