Project Euler 203

发表于 2022-05-30 更新于 2023-07-03 分类于 Project Euler 阅读次数：本文字数： 695 阅读时长 ≈ 1 分钟

Project Euler 203

题目

Squarefree Binomial Coefficients

The binomial coefficients $(\binom{n}{k})$ can be arranged in triangular form, Pascal's triangle, like this:

							1
						1		1
					1		2		1
				1		3		3		1
			1		4		6		4		1
		1		5		10		10		5		1
	1		6		15		20		15		6		1
1		7		21		35		35		21		7		1
							...

It can be seen that the first eight rows of Pascal's triangle contain twelve distinct numbers: $1, 2, 3, 4, 5, 6, 7, 10, 15, 20, 21$ and $35$ .

A positive integer $n$ is called squarefree if no square of a prime divides $n$ .

Of the twelve distinct numbers in the first eight rows of Pascal's triangle, all except $4$ and $20$ are squarefree.

The sum of the distinct squarefree numbers in the first eight rows is $105$ .

Find the sum of the distinct squarefree numbers in the first $51$ rows of Pascal's triangle.

解决方案

由于需要遍历的行数比较少，因此枚举出杨辉三角前 $51$ 行的所有数，并直接通过因式分解判断其是否为无平方数即可。

代码

from tools import get_pascals_triangle, factorization

N = 51
ans = 1
for x in set().union(*[ls for ls in get_pascals_triangle(N-1)]) - {1}:
    if max(f[1] for f in factorization(x)) == 1:
        ans += x
print(ans)