逆元知识普及（进阶篇）——from Judge
刚艹完一道 提高- 的黄题（曹冲养猪） ，于是又来混一波讲解了
——承接上文扫盲篇
四、Lucas定理(求大组合数取模)
再讲讲lucas定理这个东西(扩展lucas就不讲了,因为不大会…咳咳,然后也不怎么会用到吧)
基本公式： C(n,m) ≡ C(n/p,m/p)*C(n%p,m%p) (mod p)
(也就是： C(n,m)%p=C(n/p,m/p)*C(n%p,m%p)%p )
适用范围：n 和 m 非常大，而模数 p 比较小的情况 (偷懒)
运用：
将组合数中的 n 和 m 不断除以 p , 同时用除 p 的余数做组合数,累计入答案。
即,不断调用基本公式,递归求解,直至 m 等于 0 .
用上述例子就是：令C(n/p,m/p) ≡ C( (n/p)/p,(m/p)/p ) * C( (n/p)%p,(m/p)%p ) (mod p)
然后把 C(n/p,m/p) 求得的解 带入基本公式, 求出 C(n,m)%p 的值
证明及推导：
以下证明推导源自 Lucas定理——推导及证明
要证：C(n,m)%p=C(n/p,m/p)*C(n%p,m%p)%p
即证：C(n,m)=C(n/p,m/p)*C(n%p,m%p)
证明条件：已知p是素数，n、m、p为整数。
1.由二项式定理得： ，且
2.由费马小定理得：
（1）式 ：(x + 1) ^p ≡ x+1 (mod p) [ 由x ^p ≡ x (mod p) , x 用 (x+1) 代替得到]
（2）式 ：x ^p + 1 ≡ x+1 (mod p) [ 由x ^p ≡ x (mod p) , 等式两边同时+1得到]
合并 1 、2 两式，得到：
（3）式 ：(x + 1) ^p ≡ x ^p + 1 (mod p)
3.由 n = n/p *p + n%p . 则：
(x+1) ^p ≡ (x+1) ^(n/p *p) * (x+1)^(n%p) (mod p)
带入三式： (x+1)^p ≡ (x^p +1)^(n/p)*(x+1)^(n%p) (mod p)
将上式由二项式公式可转化为：（可以把式子写一下再看）
∑(n，z=0) C(n，z)* x^z ≡ ∑(n/p，i=0) C( n/p，i )* x^（p * i )* ∑(n%p，j=0) C(n%p，j)* x^j (mod p)
任意一个Z，必存在一个 i , j 满足：x ^ z = x ^ (p* i) * x^ j （即满足：n = n/p *p + n%p），
当且仅当： i=z/p，j=z%p 时成立
此时, C(n,m)=C(n/p,m/p)*C(n%p,m%p) 成立
证毕
代码(同上随意手打)：
//by Judge define ll long long ll mod; inline ll quick_pow(ll x,ll p){ ll ans=1; while(p){ if(p&1) ans=ans*x%p; x=x*x%p, b>>=1; } return ans; } inline ll C(ll n,ll m){ ll cn=1,cm=1,res=1; if(n<m) return 0; if(n==m) return 1; if(m>n-m) m=n-m; for(ll i=0;i<m;++i){ cn=(cn*(n-i))%mod; cm=(cm*(m-i))%mod; } res=(cn*quick_pow(cm,mod-2))%mod; //除法转换求逆元 return res; } ll Lucas(ll n,ll m){ ll ans=1; while(n && m && ans){ ans=(ans*C(n%mod,m%mod))%mod; //拆分+递归 n/=mod, m/=mod; } return ans; }
五、解线性同余方程组
其实这个玩意儿没什么高大上的，就CRT … 什么的，你是没看过 NOI day2 T1 吧，那个玩意儿…不说了，勾起了一些不美好的回忆（据说该题是所有题里面最简单的）
emmmm，首先解释一下这个东西。
线性同余方程组：
（ 求解 X ，其中 X 满足以下条件 ）
X≡b1 (mod a1)
X≡b2 (mod a2)
…
X≡bn (mod an)
对，就和上面一样，是 n 个式子，（一般）让你求出 X 的最小正整数解（即满足 n 个式子的限制条件），这里看不大懂的话你可以看看曹冲养猪这道题，那个比喻也是蛮生动的
那么这玩意儿怎么解呢？ 别急，我们得先来看看 X 有解的条件。
其实条件很简单： b2 – b1 ≡ 0 ( mod gcd(a1,a2) )
证明如下：
设 X = a1*y1+b1 , 则 a1*y1+b1 ≡ b2 (mod a2) （就是在式 2 中把 X 替换掉）
=> a1*y1≡b2 – b1 (mod a2) => a1*y1 + a2*y2 = b2 – b1
那么和逆元有解条件的证明类似，只有 (b2-b1) | gcd(a1,a2) 时，原式有解（其中 (a) | (b) 代表 a 能被 b 整除 ）
证毕
所以呢？证明完了之后有什么用处么？ 当然有。
你看啊，上面的那个式子我们推着推着就退出来了一个方程对吧？是不是有点眼熟？ （提示一下 ax + by ）
emmmm 对吧。就是类似一个扩欧的式子啊，因为 a1 和 a2 已知了啊。
然后我们用扩欧求出 a1*y1 + a2*y2 = gcd(a1,a2) 中 y1 的解就离胜利不远了
然后你看看我们解出来的这个 y1 和 y2 ，其实它并不是 a1*y1 + a2*y2 = b2 – b1 的解（这不显然嘛）
但是！ b2 – b1 是可以整除 gcd(a1,a2) 的，所以我们只需要让 y1 和 y2 乘以 (b2-b1)/gcd(a1,a2) 就可以令等式成立了
然后我们把 y1 带入 X = a1*y1+b1 不就可以得到答案了？
但是这里有个关键问题对吧（上面的这些推导只求出了 两个式子的解啊，我们不是要求满足 n 个式子的解吗？）
所以我们要考虑的就是把这个方法延续下去…也就是说我们要把 1、2 两个式子合并起来，与第 3 个式子继续进行以上操作。
怎么合并？ =》 X=X’ (mod lcm(a1,a2)) （其中 X’ 是由前两个式子得到的答案）
为什么可以这样合并？ 你只要知道 X’ 是原式在 lcm(a1,a2) 范围内唯一的解就好了（我也不知道怎么证，已经颓废到懒得想了）
然后呢…没然后了啊，然后就是代码部分了啊QAQ
代码:
int ex_gcd(int a,int b,int& x,int& y){ //本来不想附 ex_gcd 代码来着的... if(!b) { x=1,y=0;return a; } int d=ex_gcd(b,a%b,y,x); y-=a/b*x; return d; } inline ll solv(int n){ x=0,m=1; // x 记录前两个方程组的答案，初始为 0， m 记录前面所有的 a 的 lcm for(int i=1;i<=n;++i){ scanf("%lld%lld",&A,&B); int b=B-x,d=ex_gcd(m,A,z,y); if (b%d!=0) return (int)(puts("-1")); int t=b/d*z%(A/d); x=x+m*t,m*=A/d; } return x; }
好了，Judge’s Class 终于水过去了，继续刷水题去 ヾ(ToT)Bye~Bye~