Could anyone explain me the login behind the optimised code for the above link.
I was able to reduce the double sigma notation to a single sigma notation but for large value of n is timed out.
Ohk,we have to find
Summation(i=1 to n) {Summation(j=i to n){(i*j)%M} }
Which is same as
(Summation(i=1 to n) i * {Summation(j=i to n) {j} })%M
Now summation(j=i to n) {j} = (n+i)*(n-i+1)/2 (AP FORMULA)
so we have to find
(Summation(i=1 to n) { i*(n+i)*(n-i+1)/2 } )%M
= (Summation(i=1 to n) { (i*(n^2+n) + i^2 - i^3)/2 } )%M
This can easily be calculated (Summation(i)=n*(n+1)/2,…)
Use fermat for calculating a/b modM
2 Likes