algorithm - 系列之和：1^1 + 2^2 + 3^3 + ... + n^n (mod m)

Question

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

Mycode 因 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^x>m 并反复将 n^n%m 减少到 (n^x%m)^(n/x)*n^( n%x)%m。我确信这个策略是有效的。

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

你在这里被杀了吗：

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

Answer 6

我无法添加评论，但对于中国剩余定理，请参阅http://mathworld.wolfram.com/ChineseRemainderTheorem.html公式（4）-（6）。