佚名通过本文主要向大家介绍了nck面膜机,华为nck码,sim卡网络解锁nck码,nck轴承,nck码等相关知识,希望对您有所帮助,也希望大家支持linkedu.com www.linkedu.com
问题：对于很大的N和一个比较大的质数p，如何快速计算nCk % p？
描述:
解决方案1:
描述:
对于比较小的数据规模，比如说：
- P不大（P <= 10000），用Lucas定理就可以很轻松的解决，时间复杂度是O(log(n))，非常地快。
- P很大，但是n不大（P <= 10^9, n <= 100000），那根据组合的定义，计算乘法逆元就好了，如果不预处理就是O(nlogn)，也还挺快的。
但是如果数据范围达到了P <= 10^9+7, N <= 10^100，P为质数，应该如何快速计算？
解决方案1:
你是说想找到一个比利用LUCAS定理算法复杂度更低的算法吗？
N达到这个量级时，计算机存储超过330位，绕不开大数计算，而这个问题如果不考虑计算机运算位数限制的话显然LUCAS定理是最优办法，因此我觉得快速算法的核心在大数运算上