系列之和:1 ^ 1 + 2 ^ 2 + 3 ^ 3 + ... + n ^ n(mod m)

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.中国剩余定理也可能有所帮助,因为它减少了模数.