|
今天主要看了卢卡斯定理求组合数分别用费马小定理和扩展欧几里得定理实现，以及扩展的卢卡斯定理，乘法逆元和一些模板的整理。书上的卢卡斯定理讲的比较简单，跟我在博客上看到的定理不一样，一开始没反应过来。书上讲的是
之前看这个公式的时候没有思考，只是粗略的看了，想不到这个公式能怎么用，感觉很空。今天看博客上的卢卡斯定理是先将n,与m分解
然后卢卡斯定理描述为
只要仔细观察就能发现书上的公式只要依次推导就能得到下面的公式。卢卡斯定理当P为质数时较为简单，直接套模板即可。用逆元法的话，由于P是质数，能利用费马小定理求出逆元求解。或者是扩展gcd。没太大区别，只是换了个公式而已，在这些数论取模运算中，这样都是常用的工具，彼此联系。不过现在就单单这几个定理，我还没搞透彻的，题目稍微灵活点，我就想不到该用哪个了，还是要更深层次的理解应用，不过现在对于一些简单的这些定理的题，我应该还是会的。
还有一个扩展卢卡斯定理，不需要P是质数的，就是要对P分解质因数，求对质因数的模，在用中国剩余定理求解，比如计算C(10,3)%14。C(10,3)=120,14有两个质因数2和7，120%2=0,120%7=1,这样用(2,0)(7,1)找到最小的正整数8即是答案，即C(10,3)%14=8。可谓是非常巧妙了，神奇的数学。基本原理是这样，还有很多要注意的地方，已经整理了模板，中国剩余定理如果模数不为质数的话，用扩展欧几里得求解的方法也已整理。 | 
转播
