一系列的总和：1 ^ 1 + 2 ^ 2 + 3 ^ 3 + ... + N ^ N（模m） [英] Sum of series: 1^1 + 2^2 + 3^3 + ... + n^n (mod m)

问题描述

有人可以给我一个高效的算法n很大的想法（比如10 ^ 10）找到上述一系列的总和？

我的code是越来越klilled对于n = 100000和M = 200000

 ＃包括＆LT; stdio.h中＆GT;

诠释的main（）{
    INT N，M，I，J，和，吨;
    scanf函数（％D，和放大器; N，放大器; M）;
    总和= 0;
    对于（i = 1; I＆LT; = N;我++）{
    T = 1;
    为（J = 1; J＆LT; = I，J ++）
    T =（（久长）T * I​​）％米;
    总和=（总和+ T）％M;
    }
    的printf（％D \ N，总和）;

}
 

解决方案

有两点需要注意：

 （A + B + C）％M
 

等同于

 （一％的M + B％M + C％M）％M
 

和

 （A * B * C）％M
 

等同于

 （（A％M）*（B％M）*（C％M））％M
 

这样一来，你可以在O使用递归函数计算出每个学期（日志的 P 的）：

  INT expmod（INT N，INT磷，INT M）{
   如果（P == 0）返回1;
   INT纳米= N％米;
   长长的R = expmod（纳米，P / 2，M）;
   R =（R * r）的％间;
   如果（P％2 == 0）收益 -  [R;
   回报（R * NM）％米;
}
 

和使用为循环和元素：

 长长的R = 0;
的for（int i = 1; I＆LT; = N; ++ I）
    R =（R + expmod（I，I，M））％米;
 

这个算法是O（ N 的日志的 N 的）。

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

}

解决方案

Two notes:

(a + b + c) % m

is equivalent to

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

and

(a * b * c) % m

is equivalent to

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

As a result, you can calculate each term using a recursive function 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;
}

And sum elements using a for loop:

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

This algorithm is O(n log n).

这篇关于一系列的总和：1 ^ 1 + 2 ^ 2 + 3 ^ 3 + ... + N ^ N（模m）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！