我有大数K,C [1],C [2],C [3]等我必须计算b：
b = C[1]*C[2]+C[3]*C[4]+... (mod K)@H_403_4@现在我计算全部金额然后做出类似的东西
b = SUM % K.@H_403_4@但是当SUM变得大于无符号长限时,这不起作用,所以我必须使用类似的东西
b = (C[1]*C[2] %K + C[3]*C[4] %K ) %K@H_403_4@但这很费时间.我试过使用unsigned long long,除了unsigned long,这也很耗时.有没有更好的方法？ @H_403_4@UPD：
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;
}
解决方法
如果您可以将K分解为
pairwise relatively prime个数字K1,…,Kn,那么您可以对每个Ki进行计算,并使用
Chinese remainder theorem将结果合并为K的结果.这通常要快得多,特别是如果Ki适合一个机器字.
