Somma delle serie: 1^1 + 2^2 + 3^3 + ... + n^n (mod m)

Question

Qualcuno può darmi un'idea di un algoritmo efficiente per grande n (diciamo 10^10) a trova la somma delle serie precedenti?

mycode sta ottenendo klilled per n = 100000 e 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

Due note:

(a + b + c) % m 

è equivalente a

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

e

(a * b * c) % m 

è equivalente a

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

Di conseguenza, è possibile calcolare ogni termine utilizzando una funzione ricorsiva 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; 
} 

E sum elementi utilizzando un ciclo for:

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

Questo algoritmo è O (n log n).

Answer 2

Si può dare un'occhiata alla mia risposta a this post. L'implementazione è leggermente buggata, ma l'idea è lì. La strategia chiave è trovare x tale che n^(x-1) < me n^x > m e ridurre ripetutamente n^n% m in (n^x% m)^(n/x) * n^(n% x)% m. Sono sicuro che questa strategia funzioni.

Answer 3

Penso che si possa usare il teorema di Eulero per evitare qualche esponenziale, come phi (200000) = 80000. Anche il teorema del remainder cinese potrebbe essere d'aiuto in quanto riduce il modulo.

Answer 4

State essere uccisi qui:

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

Exponentials mod m potrebbero essere implementati utilizzando la somma dei quadrati metodo.

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

non posso aggiungere commenti, ma per il teorema cinese del resto, vedere http://mathworld.wolfram.com/ChineseRemainderTheorem.html formule (4) - (6).

Answer 6

Ho riscontrato di recente una domanda simile: my 'n' è 1435, 'm' è 10^10. Ecco la mia soluzione (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; 
} 

Alla fine 's' è uguale al numero richiesto.