联赛的数学知识并不多，但是还是挺重要挺基础的。
本人巨弱，有问题请指出哦。
看不明白的评论即可，或者你可以直接来找我问。
数论相关
1.裴蜀定理
一个二元线性方程:$ax+by=c$，存在解的充分必要条件为：$gcd(a,b)|c$
证明：
令$egin{array}{rcl}d & = & gcd(a,b) \ a & = & k_1d\b & = & k_2d \ax+by & = & (k_1+k_2)d=c end{array}$
所以$d|c->gcd(a,b)|c$
2.线性推逆元
$i^{-1}=(-lfloor{frac{p}{i}} floor)(p\%i)^{-1}(mod p)$
证明：
设$p=ai+b$
$ai+bequiv pequiv0 (mod p)$
$(ai+b)i^{-1}b^{-1}equiv0(mod p)$
$ab^{-1}+i^{-1}equiv0(mod p)$
$i^{-1}equiv(-ab^{-1})(mod p)$
$i^{-1}equiv (-lfloor{frac{p}{i}} floor)(p\%i)^{-1}(mod p)$
3.$Euler$函数
$phi(n)=nPi_{p^k|n}(1-frac{1}{p^k})$
引理：
如果:$gcd(a,b)=1$
$phi(ab)=phi(a)phi(b)$
证明：与$a$互质且和$b$互质，一定和$ab$互质，这样的数有$phi(a)phi(b)$个。
分类讨论：
1.n=p,$phi(n)=p-1$显然成立
2.n=p^k,$phi(n)=p^k-p^{k-1}$显然成立
3.n为任意合数，$phi(n)=Pi_{p^k|n}phi(p^k)=nPi_{p|n}(1-frac{1}{p})$
证毕。
4.欧拉定理
$a^{phi(m)}equiv 1(mod m),(gcd(a,m)=1)$
证明：
令$gcd(a,m)=1$
设集合$S={x_1,x_2...x_{phi(m)}}$中的每一个数都小于$m$且和$m$互质，而且各不相同。
那么集合$P={ax_1,ax_2...ax_{phi(m)}}$中每一个数都与$m$互质。
引理：集合$P$中的每一个数各不相同。
反证：
假设$ax_i-ax_jequiv0(mod m)$
那么$(x_i-x_j)=km$
$x_i$和$x_j$既小于$m$又是$m$的倍数，显然不成立。
所以集合$P$中的每一个数各不相同。
引理得证。
我们发现$P$在$mod m$意义下，各不相同，且均和$m$互质，同$S$的定义相同。
那么，在$mod m$意义下，$S$与$P$等价。
所以
$egin{array}{rcl} prod limits_{i=1}^{phi(m)}ax_i & equiv & prodlimits_{i=1}^{phi(m)}(mod m) \a^{phi(m)}prodlimits_{i=1}^{phi(m)}x_i & equiv & prodlimits_{i=1}{phi(m)}(mod m) \a^{phi(m)} & equiv & 1(mod m) end{array}$
5.费马小定理
$a^{p-1}equiv1(mod p),(p为质数)$
证明：
$p-1=phi(p)$
代入欧拉定理显然成立。
筛法汇总
1.埃筛质数
枚举每个数的倍数，挨个筛
组合数学相关
1.二项式定理
$(a+b)^n=sum limits_{k=0}^{n} C_n^ka^{m-k}b^k$
当$n=1$时候
$(a+b)^n=C_1^0a+C_1^1b=a+b$
二项式定理显然成立。
用数学归纳法证明。
现在假设当$n=m$的时候二项式定理成立，那么当$n=m+1$时。
$egin{array}{rcl}(a+b)^{m+1} & = & a(a+b)^m+b(a+b)^m\ & = & asum limits_{k=0}^{m}C_m^ka^{m-k}b^{k}+bsum limits_{k=0}^{m}C_m^ka^{m-k}b^{k}\ & = & a(sum limits_{k=1}^{m}C_m^ka^{m-k}+a^m)+b(sum limits_{k=0}^{m-1}C_m^ka^{m-k}b^k+b^m) \ & = & a^{m+1}+b^{m+1}+sum limits_{k=1}^{m}C_m^ka^{m-k+1}+sum limits_{k=1}^{m}C_m^{k-1}a^{m-k+1}b^{k} \ & = & a^{m+1}+b^{m+1}+sum limits_{k=1}^{m}[(C_m^k+C_m^{k-1})]a^{m-k+1}b^k \ & = & a^{m+1}+b^{m+1}+sum limits_{k=1}^{m}C_{m+1}^ka^{m-k+1}b^k \ & = & sum limits_{k=0}^{0}C_{m+1}^{k}a^{m-k+1}b^{k}+sum limits_{k=m+1}^{m+1}C_{m+1}^{k}a^{m-k+1}b^{k}+sum limits_{k=1}^{m}C_{m+1}^ka^{m-k+1}b^k \ & = & sum limits_{k=0}^{m+1}C_{m+1}^{k}a^{m+1-k}b^{k} end{array}$
得证。
2.$Lucas$定理
用二项式定理和费马小定理来证明。
设$n=kp+a,m=lp+b$
$C_n^m=C_k^lC_a^b$
由费马小定理：
$x^{p-1}equiv 1(mod p)$
$(1+x)^pequiv(1+x)^{p-1}(1+x)equiv1(1+x)equiv1+1xequiv1+x^{p-1}xequiv1+x^p (mod p)$
由二项式定理得：
$(1+x)^n=sumlimits_{i=0}^{n}C_n^ix^i$
那么接下来证明$Lucas$定理
$(1+x)^n=(1+x)^{kp}(1+x)^a$
$=(1+x^p)^k(1+x)^a$
$=sumlimits_{i=0}^kC_k^ix^{ip}sumlimits_{j=0}^aC_a^jx^j$
分离出两边$x^m$的项
$left=C_n^mx^m$
$right=C_k^lC_a^bx^{ip}x^{j}=C_k^lC_a^bx^{m}(ip+j=m -> i=l andj=b)$
$left=right$
$C_n^m=C_k^lC_a^b$
得证。