更新： C(n, k) 表示Binomial Coefficient
我正在处理一个数论问题。我已经把大问题变成了一个简单的问题： 如何计算C(n,k)%3，其中 n<=10^15。大约m ( <= 10 000 )需要在1 秒内计算的数据集。
我解决它的方法是使用Lucas' theorem. 是O(m log n)。而且它的速度足以解决问题。但我想知道这个问题是否有更好的解决方案，甚至是n <= 10^100orm <= 1 000 000？
非常感谢！
问问题
217 次