若 t = 1 , a ^ ( p - 2 ) 为 a 在取模 p 意义下的乘法逆元
通常用 inv 表示
证明：
b * a =（三等）1（mod p）
a ^ ( p - 2 ) * a =（三等）1（mod p）
把两个阶乘拆开,发现组合数只与 n！、（n！）^ ( p - 2 ) 有关
辗转相除法（欧几里得算法）
证明：
d=gcd(a,b) a=xd b=yd a-b=(x-y)d
gcd(b,a-b)
假设存在t>1 , t|y , t|x-y , 推出t|x , t|y , 推出t|a , t|b , gcd(a,b) = td , 与题目描述矛盾
一个偶数a和另一个数字b的gcd一定等于 a/2 与b的gcd
所以就可以用位运算来优化
如果两个偶数求gcd 那就先都除以2
如果两个都是奇数，那就用更相减损术（其实和欧几里得没大有区别）