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;
}
CodePudding user response:
(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.