对于很大的N和一个比较大的质数p,如何快速计算nCk % p?

发布于 2022-08-24 13:49:57 字数 377 浏览 20 评论 0

对于比较小的数据规模,比如说:

- 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 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(1

蓝眼睛不忧郁 2022-08-31 13:49:57

你是说想找到一个比利用LUCAS定理算法复杂度更低的算法吗?
N达到这个量级时,计算机存储超过330位,绕不开大数计算,而这个问题如果不考虑计算机运算位数限制的话显然LUCAS定理是最优办法,因此我觉得快速算法的核心在大数运算上

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文