拓展中国剩余定理 EXCRT模板 and 拓展卢卡斯定理 EXLUCAS模板

EXCRT

学习地址：C20182030太强了 博客里面的证明很易懂。 博客里面数论的各个Part都值得一看。

比较简洁的写法： 扩展中国剩余定理： 模数不一定互质，将方程依次合并： $\{\begin{array}{l}x\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}b)\\ x\equiv c(\mathrm{m}\mathrm{o}\mathrm{d}d)\end{array}$ 可知 $b\cdot t+a\equiv c(\mathrm{m}\mathrm{o}\mathrm{d}d)$ 用$\text{exgcd}$求出$t\equiv \frac{c-a}{(b,d)}\ast (\frac{b}{(b,d)}{)}^{-1}(\mathrm{m}\mathrm{o}\mathrm{d}\frac{d}{(b,d)})$ 代回得$x\equiv b\cdot t+a(\mathrm{m}\mathrm{o}\mathrm{d}[b,d])$ 易验证$x$满足原方程，且方程的通解为$x+k[b,d]$

Code（洛谷P4777）：

#include<bits/stdc++.h> #define maxn 100005 #define LL long long using namespace std; inline LL mul(LL a,LL b,LL p){return (a*b-(LL)((long double)a*b/p)*p+p)%p;} LL gcd(LL a,LL b){return b?gcd(b,a%b):a;} void exgcd(LL a,LL b,LL &x,LL &y){ if(!b) x=1,y=0; else exgcd(b,a%b,y,x),y-=a/b*x; } int main() { int n; LL A1,P1,A2,P2,x,y,d,lcm; scanf("%d%lld%lld",&n,&P1,&A1); while(--n){ scanf("%lld%lld",&P2,&A2),d=gcd(P1,P2); exgcd(P1/d,P2/d,x,y),lcm=P1/d*P2; A1=(mul(mul((A2-A1)/d,x,lcm),P1,lcm)+A1)%lcm; P1=lcm; } printf("%lld\n",(A1+P1)%P1); }

---

EXLUCAS

学习地址：讲的很清楚

求组合数 $\frac{n!}{m!(n-m)!}$ 模$p^k$ 首先求出上下除去$p$的因子后模$p^k$的值，然后求出下面模$p^k$的逆元。

于是问题就是怎么求$n!$除去$p$的因子后模$p^k$的值。

首先除去$n!$中$p$的倍数，那么被除的数形成了$(\frac{n}{p})!$，递归计算。剩下的数不包含$p$的因子，形成了$[1,p^k)$内不包含$p$的因子的这一段的$\frac{n}{p^k}$次重复，暴力把$[1,p^k)$以内乘起来然后快速幂，剩下的非整段的长度$<p^k$，同样暴力乘起来。 预处理$p^k$以内不含$p$因子的数的前缀积，每次递归就只需要一次快速幂了，总复杂度就是$O(p^k+\log n)$

但是有时候我们会遇到$p^k$和$n$很大，但$m$较小的情况，这时候可以把组合数表示为 $\frac{n^{\underline{m}}}{m!}$，直接$for$循环除去$p$的因子，然后剩下的求逆元模就好了。这样复杂度是$O(m\log m)$的。