我有大数 K
、C[1]
、C[2]
、C[3]
等等,我必须计算 b:
b = C[1]*C[2]+C[3]*C[4]+... (mod K)
现在我计算总和,然后做类似的事情
b = SUM % K.
但是当 SUM 变得比 unsigned long limit 大时,这是行不通的,所以我必须使用类似的东西
b = (C[1]*C[2] %K + C[3]*C[4] %K ) %K
但这很耗时。我尝试使用 unsigned long long 除了 unsigned long 之外,这也很耗时。有没有更好的办法?
更新:
C = (unsigned long long int *) malloc(N*sizeof(unsigned long long int));
unsigned long int i, j, l;
C[0] = 1;
for (i=1; i<=N; i++) {
C[i] = 0;
l = (unsigned long int) i/2;
for (j=0; j<l; j++) {
C[i] += C[j]*C[i-j-1];
C[i] = C[i] % K;
}
C[i] = C[i]*2;
C[i] = C[i] % K;
if (i - l*2 == 1) {
C[i] += C[l]*C[l];
}
C[i] = C[i] % K;
}
最佳答案
模 m 算术是环同态。
然后说 f(x) = x%P
f(a+b) = f(a)+f(b) 还有
f(a*b) = f(a)*f(b)
http://en.wikipedia.org/wiki/Modular_arithmetic
这意味着你可以在每一步之后做一个 mod P。
关于c - 求和乘法模,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6008312/