对于很大的N和一个比较大的质数p,如何快速计算nCk % p?
对于比较小的数据规模,比如说:
- P
不大(P <= 10000
),用Lucas定理
就可以很轻松的解决,时间复杂度是O(log(n))
,非常地快。
- P
很大,但是n
不大(P <= 10^9, n <= 100000
),那根据组合的定义,计算乘法逆元就好了,如果不预处理就是O(nlogn)
,也还挺快的。
但是如果数据范围达到了P <= 10^9+7, N <= 10^100
,P为质数,应该如何快速计算?
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(1)
你是说想找到一个比利用LUCAS定理算法复杂度更低的算法吗?
N达到这个量级时,计算机存储超过330位,绕不开大数计算,而这个问题如果不考虑计算机运算位数限制的话显然LUCAS定理是最优办法,因此我觉得快速算法的核心在大数运算上