对于比较小的数据规模,比如说:
- P
不大(P <= 10000
),用Lucas定理
就可以很轻松的解决,时间复杂度是O(log(n))
,非常地快。
- P
很大,但是n
不大(P <= 10^9, n <= 100000
),那根据组合的定义,计算乘法逆元就好了,如果不预处理就是O(nlogn)
,也还挺快的。
但是如果数据范围达到了P <= 10^9+7, N <= 10^100
,P为质数,应该如何快速计算?
你是说想找到一个比利用LUCAS定理算法复杂度更低的算法吗?
N达到这个量级时,计算机存储超过330位,绕不开大数计算,而这个问题如果不考虑计算机运算位数限制的话显然LUCAS定理是最优办法,因此我觉得快速算法的核心在大数运算上