Сумма серий: 1 ^ 1 + 2 ^ 2 + 3 ^ 3 + ... + n ^ n (мод м)

Question

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

Мой код уничтожается при n = 100000 и 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

Две ноты:

(a + b + c) % m

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

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

и

(a * b * c) % m

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

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

В результате вы можете вычислить каждый член, используя рекурсивную функцию в 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;
}

И суммируйте элементы, используя цикл 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

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

Answer 3

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

Answer 4

Недавно я столкнулся с похожим вопросом: у меня 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' равно требуемому числу.

Answer 5

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

Answer 6

Тебя убивают здесь:

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

Экспоненты mod m могут быть реализованы с использованием метода суммы квадратов.

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