Сумма ряда: 1^1 + 2^2 + 3^3 + ... + n^n (mod m)

Question

Может ли кто-нибудь дать мне представление об эффективном алгоритме для больших n (например, 10^10) найти сумму вышеуказанных серий?

Mycode становится klilled при п = 100000 т = 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

Два примечания:

(a + b + c) % m 

эквивалентно

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

и

(a * b * c) % m 

эквивалентно

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

В результате, можно вычислить каждый член с помощью рекурсивной функции в O (журнал р):

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

и сумма элементов с использованием for цикла:

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

Этот алгоритм является O (n log n).

Answer 2

Возможно, вы найдете мой ответ на вопрос this post. Реализация там немного глючит, но идея есть. Ключевой стратегией является найти x, для которого n^(x-1) < m и n^x > m и несколько раз уменьшать n^n% m до (n^x% m)^(n/x) * n^п% х)% м. Я уверен, что эта стратегия работает.

Answer 3

Я думаю, вы можете использовать теорему Эйлера, чтобы избежать некоторой экспоненты, так как phi (200000) = 80000. Теорема о китайском остатке может также помочь, поскольку она уменьшает модулю.

Answer 4

Вы убитые здесь:

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

Exponentials тойт может быть реализован с использованием методы суммы квадратов.

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

Я не могу добавить комментарий, но для китайской теореме об остатках, см http://mathworld.wolfram.com/ChineseRemainderTheorem.html формулы (4) - (6).

Answer 6

Недавно я столкнулся с похожим вопросом: my 'n' равно 1435, 'm' составляет 10^10. Вот мое решение (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; 
} 

В конце 's' равен требуемому номеру.