Suma de series: 1^1 + 2^2 + 3^3 + ... + n^n (mod m)

Question

¿Puede alguien darme una idea de un algoritmo eficiente para n grande (digamos 10^10) para encontrar la suma de las series anteriores?

MyCode está consiguiendo klilled para n = 100.000 y 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); 

} 

Answer 1

Dos notas:

(a + b + c) % m 

es equivalente a

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

y

(a * b * c) % m 

es equivalente a

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

Como resultado, se puede calcular cada término usando una función recursiva en 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; 
} 

y la suma de elementos utilizando un bucle for:

long long r = 0; 
for (int i = 1; i <= n; ++i) 
    r = (r + expmod(i, i, m)) % m; 

Este algoritmo es O (n log n).

Answer 2

Puede echar un vistazo a mi respuesta al this post. La implementación allí es un poco falsa, pero la idea está ahí. La estrategia clave es encontrar x tal que n^(x-1) < m y n^x > my reducir repetidamente n^n% m a (n^x% m)^(n/x) * n^(n% x)% m. Estoy seguro de que esta estrategia funciona.

Answer 3

Creo que puede usar el teorema de Euler para evitar alguna exponenciación, como phi (200000) = 80000. El teorema del resto chino también podría ayudar, ya que reduce el módulo.

Answer 4

¿Usted está consiguiendo mató aquí:

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

Exponenciales mod m podrían ser implementados utilizando el método de suma de cuadrados.

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; 
} 

Answer 5

No puedo añadir comentarios, pero para el teorema chino del resto, ver http://mathworld.wolfram.com/ChineseRemainderTheorem.html fórmulas (4) - (6).

Answer 6

Me encontré con una pregunta similar recientemente: my 'n' es 1435, 'm' es 10^10. Aquí está mi solución (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; 
} 

Al final 's' es igual al número requerido.