谁能给我一个大 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);
}
最佳答案
两个注意事项:
(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)。
关于algorithm - 序列总和 : 1^1 + 2^2 + 3^3 + . .. + n^n (mod m),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45282808/