Sum of series: 1^1 + 2^2 + 3^3 + ... + n^n (mod m)

Asked
Viewd29883

8

Can someone give me an idea of an efficient algorithm for large n (say 10^10) to find the sum of above series?

Mycode is getting klilled for n= 100000 and 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);

}
  • Oh, and O(m log m) time for calculating the cached values using Mehrdad’s code. So if m grows with n, it’s probably no help at all, but if m is bounded it’s probably an improvement.

    Steve Jessop01 октября 2009, 12:09
  • Авиатор: Эффективные алгоритмы обычно не зависят от языка. Не имеет значения, Java это или C (кроме, может быть, линейного фактора времени выполнения).

    Joey01 октября 2009, 10:08
  • @ Йоханнес: Я понимаю. Я подумал о том, чтобы предложить BigInteger. Вот почему спросил

    vpram8601 октября 2009, 10:09
  • Подумав об этом, вы можете также кэшировать 1 ^ 2m… (m-1) ^ 2m, пока вы вычисляете члены 2m + 1… 3m-1. Затем используйте эти значения для вычисления 1 ^ 3m… (m-1) ^ 3m и замените сохраненное значение новым значением для использования при вычислении 1 ^ 4m… (m-1) ^ 4m. Без написания кода я понятия не имею, будет ли это на самом деле быстрее, чем solutino Мехрдада, но если я не пропустил что-то фатальное, это O (n) вместо O (n log n). Однако очевидно, что требуется O (m) памяти.

    Steve Jessop01 октября 2009, 12:04
  • You say you want something fast for big n (10^10), but you don’t say whether m is similarly big, or if it stays around 200k. It might matter, because if m is small then you can try pre-calculating/caching some terms. If you already know a^m and a^a for all a less than m, then when you come to calculate (m+2)^(m+2) then it’s just 2^(m+2) = 2^m2^2. Then (m+3)^(m+3) = 3^m3^3 and so on. You can probably arrange things so that you always access your stored values sequentially, not sure.

    Steve Jessop01 октября 2009, 11:59

6 ответов

24

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

 (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 ).

  • @rahul. In case of n=1000 and m=2000, result 1000^1000%2000 to (1000^2%2000)^500%2000.

    user17281801 октября 2009, 10:11
  • @rahul: ваш внутренний j-цикл выполняется за O (i). Функция Мердада выполняется в O (log i). Замените свой внутренний цикл вызовом функции Мехрдада, и вы получите большое ускорение.

    dave442001 октября 2009, 10:10
  • Для небольших чисел делаю то же самое. Но его убивают при n = 1000000 и m = 200000. Я добавил код

    01 октября 2009, 10:01
  • rahul: No exceptions for me. It just takes a long time.

    Mehrdad Afshari01 октября 2009, 10:58
  • Я считаю, что вам нужен еще один "мод" в этих уравнениях: "(a% m + b% m + c% m)% m" и "(a% m) * (b% m) * (c % m)% m '.

    Groo01 октября 2009, 10:06
  • It is getting killed with expmod function also for n= 1000000000

    01 октября 2009, 10:44
  • Groo: Ага, сделал это в коде, пропустил в уравнениях. Спасибо. Исправлено.

    Mehrdad Afshari01 октября 2009, 10:08
0

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

5

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

  • You need to compute phi only once. Euler’s theorem says that a^phi(b)=1 mod b if (a,b)=1. Then you can simplify a^c mod b to the form a^c’ mod b where c’

    01 октября 2009, 10:35
  • Tip - try to edit your answer. Elaborate. Describe and explain your suggested algorithm. Try to post some code. Link to Wikipedia. Also, isn’t the Chinese remainder theorem used for a set of equations?

    Kobi01 октября 2009, 11:04
  • Это не имеет значения, поскольку мы можем сократить некоторые термины. Is (a, b)> 1, тогда вам следует выполнить полное возведение в степень. Легко проверить, делится ли число на 2 или 5.

    01 октября 2009, 10:49
  • Euler’s theorem and Chinese reminder theorem are easy to look up, and they are both (in conjunction) perfectly relevant here — use Euler’s theorem to compute the sum mod each prime power in m, and use CRT to put them together.

    ShreevatsaR01 октября 2009, 22:52
  • Jaska: It’s irrelevant here. What if (a,b) != 1?

    Mehrdad Afshari01 октября 2009, 10:43
  • This does ring some bells, but I’m afraid you’ll have to explain. Also, iirc, computing phi isn’t trivial.

    Kobi01 октября 2009, 10:26
1

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

3

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

0

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

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

Показатели по модулю 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;
}