c++ - Fast Modulo for N^2 formula -

i have problem, when trying resolv ecuation,

( 1*1 + 2*2 + ... + n*n ) % 10234573

my solution in c++,

#include <iostream> #include <cmath>  using namespace std; int main() {     unsigned long long int n, s= 0;     cin >> n;     if (n%10234573 == 0)     {         cout << 0;     }     else     {         cout << n*(n+1)*((2*n+1))/6 % 10234573;     }     return 0; } 

i need solution numbers bigger 10^9 + fast one.

to handle bigger number problem, need use number 10234573 in more efficient way.

we know mod, have:

(m*n) mod x = ((m mod x)*(n mod x)) mod x 

to use above formula in our calculation:

n*(n+1)*((2*n+1))/6 % 10234573 

we need rid of dividing 6.

we know divide number 6, need divide 2 , 3.

so have

unsigned long long int mod = 10234573;  unsigned long long int data[3] = {n, n + 1, 2*n + 1};  bool dividedbytwo = false; bool dividedbythree = false;  for(int = 0; < 3; i++){     if(data[i] % 2 == 0 && !dividedbytwo){        data[i]/=2;        dividedbytwo = true;      }     if(data[i] % 3 == 0 && !dividedbythree){        data[i]/=3;        dividedbythree = true;      } } //finally, applying mod our formula cout<< ((((data[0]%mod)*(data[1]%mod))%mod)*(data[2]%mod))%mod;