1. 阶乘的因数个数#

考虑一个正整数$n$的阶乘$n!$，求它有多少个质因数$p$，即求最大$i$，使$n!=kp^i$

显然，所有$p$的倍数都含有至少一个因数$p$，从$1$到$n$的$n$个数中有$\lfloor\dfrac{n}{p}\rfloor$个数是$p$的倍数

同样的，所有$p^2$的倍数都含有至少两个因数$p$，从$1$到$n$的$n$个数中有$\lfloor\dfrac{n}{p^2}\rfloor$个数是$p^2$的倍数

以此类推，所有$p^j$的倍数都含有至少$i$个因数$p$，从$1$到$n$的$n$个数中有$\lfloor\dfrac{n}{p^j}\rfloor$个数是$p^i$的倍数

当然，$p^2$的倍数也是$p$的倍数，$p^j$的倍数也是$p^{j-1}$的倍数，所以我们可以认为，每个$p^2$的倍数都在$p$倍数的基础上多一个因子$p$，每个$p^{j}$的倍数都在$p^{j-1}$倍数的基础上多一个因子$p$，那么我们就得出了最后的式子

$i= \lfloor\dfrac{n}{p}\rfloor+\lfloor\dfrac{n}{p^2}\rfloor+\lfloor\dfrac{n}{p^3}\rfloor+\cdots$

2. 二进制与组合数奇偶#

对于一个组合数$C^m_n=\dfrac{n!}{m!(n-m)!}$，要讨论它的奇偶，也就是看它分子分母含因子$2$的情况

设$a,b,c$分别为$n!,m!,(n-m)!$含因子$2$的数目

$C^m_n\mod{2}=\begin{cases}0,a>b+c\\1,a\le b+c\end{cases}$

显然，$a<b+c$时，$C^m_n$中会产生$2$的负次幂，而$C^m_n$是一个整数，所以$a$不可能小于$b+c$

所以有

$C^m_n\mod{2}=\begin{cases}0,a\ne b+c\\1,a= b+c\end{cases}$

那么我们来分析$a,b,c$

以$a$为例，$a=\lfloor\dfrac{n}{2}\rfloor+\lfloor\dfrac{n}{2^2}\rfloor+\lfloor\dfrac{n}{2^3}\rfloor+\cdots$

设$n=a_0\times 2^0+a_1\times 2^1+a_2\times 2^2+\cdots+a_i\times 2^i$，有

$a=\lfloor\dfrac{a_0\times 2^0+a_1\times 2^1+\cdots+a_i\times 2^i}{2}\rfloor+\lfloor\dfrac{a_0\times 2^0+a_1\times 2^1+\cdots+a_i\times 2^i}{2^2}\rfloor+\cdots+\lfloor\dfrac{a_0\times 2^0+a_1\times 2^1+\cdots+a_i\times 2^i}{2^i}\rfloor\\=\dfrac{a_1\times 2^1+a_2\times 2^2+\cdots+a_i\times 2^i}{2}+\dfrac{a_2\times 2^2+a_3\times 2^3+\cdots+a_i\times 2^i}{2^2}+\cdots+\dfrac{a_i\times 2^i}{2^i}\\=(a_1+a_2\times 2^1+\cdots+a_i\times 2^{i-1})+(a_2+a_3\times 2^1+\cdots+a_i\times 2^{i-2})+\cdots+a_i\\=a_1+a_2(2^0+2^1)+a_3(2^0+2^1+2^2)+\cdots+a_i(2^0+2^1+\cdots+2^{i-1})\\=a_0(2^0-1)+a_1(2^1-1)+a_2(2^2-1)+\cdots+a_i(2^i-1)\\=\sum^{i}_{j=0}{a_j(2^j-1)}=\sum^{i}_{j=0}{a_j2^j}-\sum^{i}_{j=0}a_j=n-\sum^{i}_{j=0}a_j$

不难发现，$\sum^{i}_{j=0}a_j$就是$n$的二进制中$1$的数目

同理可得，$b=m-\sum^{i}_{j=0}b_j,c=n-m-\sum^{i}_{j=0}c_j$

则$a=b+c\Longleftrightarrow n-\sum^{i}_{j=0}a_j = m-\sum^{i}_{j=0}b_j + n-m-\sum^{i}_{j=0}c_j\Longleftrightarrow \sum^{i}_{j=0}a_j = \sum^{i}_{j=0}b_j+\sum^{i}_{j=0}c_j$

也就是说，$n$二进制中$1$的数目等于$m$二进制中$1$的数目和$n-m$二进制中$1$的数目之和

换句话说，$m$二进制中有几个$1$，$n-m$时$n$的二进制中就减少几个$1$

来到二进制减法中，对于$m$中某个为$1$的位，如果$n$中对应位为$1$，那么计算减法时$n$就刚好减少一个$1$，而如果$n$中对应位为$0$，则必然产生退位$(n\ge m)$，必然增加$n$中$1$的个数，因此，对于$m$中所有为$1$的位，只有$n$中每个对应位都为$1$时，上述式子才会成立

用按位与$(\&)$描述这一条件就是$n\&m=m$

综上，我们得出结论$C^m_n\mod2=\begin{cases}0,n\&m\ne m\\1,n\&m=m\end{cases}$