# [ACCEPTED]-Sum of series: 1^1 + 2^2 + 3^3 + ... + n^n (mod m)-series

Two notes:

```
(a + b + c) % m
```

is equivalent to

```
(a % m + b % m + c % m) % m
```

and

```
(a * b * c) % m
```

is equivalent 4 to

```
((a % m) * (b % m) * (c % m)) % m
```

As a result, you can calculate each term 3 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 2 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 1 is O(*n* log *n*).

I think you can use Euler's theorem to avoid 3 some exponentation, as phi(200000)=80000. Chinese 2 remainder theorem might also help as it 1 reduces the modulo.

You may have a look at my answer to this post. The 5 implementation there is slightly buggy, but 4 the idea is there. The key strategy is to 3 find x such that n^(x-1)<m and n^x>m 2 and repeatedly reduce n^n%m to (n^x%m)^(n/x)*n^(n%x)%m. I 1 am sure this strategy works.

I encountered similar question recently: my 3 'n' is 1435, 'm' is 10^10. Here is my solution 2 (C#):

```
ulong n = 1435, s = 0, mod = 0;
mod = ulong.Parse(Math.Pow(10, 10).ToString());
for (ulong i = 1; i <= n;
{
ulong summand = i;
for (ulong j = 2; j <= i; j++)
{
summand *= i;
summand = summand % mod;
}
s += summand;
s = s % mod;
}
```

At the end 's' is equal to required 1 number.

Are you getting killed here:

```
for(j=1;j<=i;j++)
t=((long long)t*i)%m;
```

Exponentials 2 mod m could be implemented using the sum 1 of squares method.

```
n = 10000;
m = 20000;
sqr = n;
bit = n;
sum = 0;
while(bit > 0)
{
if(bit % 2 == 1)
{
sum += sqr;
}
sqr = (sqr * sqr) % m;
bit >>= 2;
}
```

I can't add comment, but for the Chinese 1 remainder theorem, see http://mathworld.wolfram.com/ChineseRemainderTheorem.html formulas (4)-(6).

More Related questions

We use cookies to improve the performance of the site. By staying on our site, you agree to the terms of use of cookies.