关于n!的问题:求n!中有多少个质因子p
非递归版本1 | #include <iostream> |
1 | #include <iostream> |
计算Cnm
利用公式Cnm=C(n-1)(m)+C(n-1)(m-1)计算1 | #include <iostream> |
1 | #include <iostream> |
计算Cnm%p
方法1
适合的条件n<=10000,m<=10000,p<10^9 最朴素的做法就是在问题2求Cnm的基础上直接在过程中取模1 | long long res[67][67]; |
方法2
适合的条件n<=10^6,m<=10^6,p<10^9 根据公式Cnm=n!/(m!*(n-m)!)计算 我们可以计算通过一开始说的阶层问题计算出n!、m!、(n-m)!的质因子的个数然后通过快速幂将质因子都乘起来就得到了Cnm的值1 | #include <iostream> |
方法3
适合的条件n<=10^18,m<=10^18,p<10^5 Lucas定理(要求p是素数) ![](/photos/c1.png)1 | #include <iostream> |
本文作者: jiangyuhao
本文链接: http://example.com/2022/06/07/%E7%BB%84%E5%90%88%E6%95%B0/
版权声明: 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处!