我想计算在模142857下的nCr。以下是我在Java中的代码:
这个算法可以在
private static int nCr2(int n, int r) {
if (n == r || r == 0) {
return 1;
}
double l = 1;
if (n - r < r) {
r = n - r;
}
for (int i = 0; i < r; i++) {
l *= (n - i);
l /= (i + 1);
}
return (int) (l % 142857);
}
这个算法可以在
O(r)
时间内计算nCr。我希望能有一个比这更快的算法来得到结果。是否有这样的算法?
n
可以变得那么大,我甚至认为double
已经不足以容纳中间结果了。 - ajbMath.ulp(l)
比142857
更大时,取模运算将更早地失去有用的结果。 - Holger