Project Euler 228

发表于 2022-06-13 更新于 2025-12-23 分类于 Project Euler 阅读次数：本文字数： 1k 阅读时长 ≈ 1 分钟

Project Euler 228

题目

Minkowski Sums

Let $S_n$ be the regular $n$-sided polygon – or shape – whose vertices $v_k (k=1,2,\dots,n)$ have coordinates:

$x_k= \cos\left(\dfrac{2k-1}{n} \times 180°\right)\quad y_k= \sin\left(\dfrac{2k-1}{n} \times 180°\right)$

Each $S_n$ is to be interpreted as a filled shape consisting of all points on the perimeter and in the interior.

The Minkowski sum, $S+T$, of two shapes $S$ and $T$ is the result of adding every point in $S$ to every point in $T$, where point addition is performed coordinate-wise: $(u,v) + (x,y) = (u+x,v+y)$.

For example, the sum of $S_3$ and $S_4$ is the six-sided shape shown in pink below:

How many sides does $S{1864}+S{1865}+\dots+S_{1909}$ have?

解决方案

这个页面描述了求两个凸包$P,Q$的闵可夫斯基和的方法：

分别逆时针沿着两个正$n$多边形$P,Q$的边界行走，枚举出$n$个边界的向量（如下图所示）。
将这些向量按照极角进行排序。
按顺序将这些向量首尾拼接，那么拼接出来的必定是一个封闭图形。这个图形就是$P,Q$的闵可夫斯基和。

回到题目中，在求闵可夫斯基和的第三个步骤中，如果两个向量的极角相同，那么说明构造出来的新凸包中，这两个向量构造的边界实际上是同一条。

因此，问题就转化为了这些边界中，总共有多少个向量是极角不同的。

以$y$轴正半轴为基准，那么不难发现，正$n$变形的边界的极角分别是$0,\dfrac{1}{n}\cdot 2\pi,\dfrac{2}{n}\cdot 2\pi,\dots,\dfrac{n-1}{n}\cdot 2\pi$。

那么问题进一步转化成：分母在范围$1864\sim 1909$的真分数中，一共有多少个不同值的分数（包括$0$）？

代码

from fractions import Fraction

L, R = 1864, 1909
ans = len(set(Fraction(i, j) for j in range(L, R + 1) for i in range(j)))
print(ans)