203. 无平方因子二项式系数(Squarefree Binomial Coefficients)
二项式系数\(C_n^k\)可以如下排成一个三角形，称为帕斯卡三角形：
$$ {\displaystyle {\begin{array}{c}1\\1\quad 1\\1\quad 2\quad 1\\1\quad 3\quad 3\quad 1\\1\quad 4\quad 6\quad 4\quad 1\\1\quad 5\quad 10\quad 10\quad 5\quad 1\\1\quad 6\quad 15\quad 20\quad 15\quad 6\quad 1\\1\quad 7\quad 21\quad 35\quad 35\quad 21\quad 7\quad 1\\\end{array}}} $$可以看出帕斯卡三角的前八行包含了十二个不同的数：$$ 1, 2, 3, 4, 5, 6, 7, 10, 15, 20, 21,35 $$如果正整数\(n\)不被任何素数的平方整除，\(n\)就被称为无平方因子数。在帕斯卡三角形前八行的十二个不同的数中，除了\(4\)和\(20\)之外都是无平方因子数,这些不同的无平方因子数之和为\(105\)。求帕斯卡三角形前\(51\)行所有不同的无平方因子数之和。
分析：这个题目可以在勒让德定理的基础上比较容易地解决，这个定理可以表述为：对于\(n!\)，记其质因数分解中质数\(p\)的指数为\(v_p\)，则有:
$$
\nu _{p}(n!)=\sum _{{i=1}}^{{\infty }}\left\lfloor {\frac {n}{p^{i}}}\right\rfloor ,
$$
如对于\({\displaystyle 6!=720=2^{4}\cdot 3^{2}\cdot 5^{1}}\)，我们有：
$$
{\displaystyle {\begin{aligned}\nu _{2}(6!)&=\sum _{i=1}^{\infty }\left\lfloor {\frac {6}{2^{i}}}\right\rfloor =\left\lfloor {\frac {6}{2}}\right\rfloor +\left\lfloor {\frac {6}{4}}\right\rfloor =3+1=4,\\[3pt]\nu _{3}(6!)&=\sum _{i=1}^{\infty }\left\lfloor {\frac {6}{3^{i}}}\right\rfloor =\left\lfloor {\frac {6}{3}}\right\rfloor =2,\\[3pt]\nu _{5}(6!)&=\sum _{i=1}^{\infty }\left\lfloor {\frac {6}{5^{i}}}\right\rfloor =\left\lfloor {\frac {6}{5}}\right\rfloor =1.\end{aligned}}}
$$
显然质因数分解的结果和通过勒让德定理计算的结果是一致的，已知\(C_n^r=\frac{n!}{(n-r)!r!}\)，则有：
$$
v_{p}\left( C^{r}_{n}\right) =v_{p}( n!) -v_{p}(( n-r) !) -v_{p}( r!)
$$
对于某一个素数\(p\)，如果\(p^2>n\)，则显然\(\left\lfloor \frac{n}{p^{2}}\right\rfloor =0\)，则有\(v_{p}( n!) =\left\lfloor \frac{n}{p}\right\rfloor\)，故上式变为：
$$
v_{p}\left( C^{r}_{n}\right) =\left\lfloor \frac{n}{p}\right\rfloor -\left\lfloor \frac{n-r}{p}\right\rfloor -\left\lfloor \frac{r}{p}\right\rfloor \le\left\lceil \frac{r}{p}\right\rceil -\left\lfloor \frac{r}{p}\right\rfloor = 1
$$
也就是说对于\(p>\sqrt{n}\)的素数，其指数最大只能为一，所以不可能是\(C_n^r\)的素数平方因子。题目中\(n\)最大只能为\(51\)，所以有可能成来平方因子的素数小于\(\sqrt{51}\approx7.14\)，则只需要考察七及七以下的素数就可以了。
代码实现上，我们可以很方便的生成帕斯卡三角，然后对帕斯卡三角中的数分别检查其是否被\(2,3,5,7\)的平方整除，如果可以整除则拥有一个素数平方因子，不满足题目条件。需要注意提，帕斯卡三解是左右对称的，所以只需要检查左边帕斯卡三解的数字就可以了。如果四个素数的平方均不能整除，则不存在素数平方因子，可以记录在集合中(方便去重)，最后我们计算这个集合的和就可以了。代码如下：
# time cost = 465 µs ± 3.78 µs
def main(n=51):
squares = [4,9,25,49]
res = set()
pt = [1,1]
for r in range(n-2):
pt = [x+y for x,y in zip(pt+[0],[0]+pt)]
for comb in pt[:(r+3)//2+2]:
if all([comb%s for s in squares]) != 0:
res.add(comb)
return sum(res)