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.

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