Modular sum of square numbers in C++ So I've got an assignment which sounds like this: 


  Given a number n, calculate the result of this sum, modulo 10,234,573:
  12 + 22 + 32 + … + n2 


This is what I've come up with :

 #include &lt;iostream&gt;
 using namespace std;

 int main()
 {
     uint n;
     cin &gt;&gt; n;

     uint num{10234573};
     uint64_t sum{0};
     for (uint i = 1; i &lt;= n; ++i) {
         sum += (i*i)%num;
         sum %= num;
     }

     cout &lt;&lt; sum;

     return 0;
 }


And I can check my algorithm on a website, but it tells me that it is "too slow"... How can I optimise it so it will be faster?
I know there is a formula for this, but the given number n can be as big as 2,000,000,000, so it will obviously overflow...
To use the modulo in equations, You need to maintain the equivalence of the Equation. The Equation you wrote in comment is not according to equivalence. See Division Under Equivalences

So, going by the equivalence you have to calculate it like this :


  [ ( (n) %x ) * ( (n+1) %x ) * ( ( 2*n + 1 ) %x ) ) * ( (1/6)%x ) ] %x 


Have a look at this.

Note that this will not work If given n is any multiple of x. So, n &amp; x must be Co-prime. In your case, x = 10234573 is already a prime number as pointed by Toby's Comment