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)