Sum of series: 1^1 + 2^2 + 3^3 + ... + n^n (mod m)
algorithm, series
Solution
Two notes:
(a + b + c) % m
is equivalent to
(a % m + b % m + c % m) % m
and
(a * b * c) % m
is equivalent to
((a % m) * (b % m) * (c % m)) % m
As a result, you can calculate each term using a recursive function in O(log p):
int expmod(int n, int p, int m) {
if (p == 0) return 1;
int nm = n % m;
long long r = expmod(nm, p / 2, m);
r = (r * r) % m;
if (p % 2 == 0) return r;
return (r * nm) % m;
}
And sum elements using a `for` loop:
long long r = 0;
for (int i = 1; i <= n; ++i)
r = (r + expmod(i, i, m)) % m;
This algorithm is O(n log n).
Problem
Can someone give me an idea of an efficient algorithm for large n (say 10^10) to find the sum of above series? Mycode is getting klilled for n= 100000 and m=200000 ``` #include<stdio.h> int main() { int n,m,i,j,sum,t; scanf("%d%d",&n,&m); sum=0; for(i=1;i<=n;i++) { t=1; for(j=1;j<=i;j++) t=((long long)t*i)%m; sum=(sum+t)%m; } printf("%d\n",sum); } ```