CF1208G Polygons

给定 $n,k$,需要建出 $k$ 个有相同外接圆的正 $a_i$ 边形,其中 $3\le a_i\le 10^6$ 且 $a_i$ 两两不同。
可以旋转任意正多边形,如果多个正多边形与外接圆的交点重合,则只算与外接圆有一个交点。现问最少与外接圆有多少交点。
$3\le n\le 10^6,1\le k\le n-2$。

$\texttt{Solution}$

首先显然所有多边形会有一个共同的与外接圆的交点。

对于一个正 $a$ 边形和一个正 $b$ 边形,如果 $a|b$,则显然 $a$ 比 $b$ 更先被选到。因为 $a$ 与外接圆的任意交点 $b$ 都有,则贪心地优先选交点更少的。

那么现在就可以得到:如果要选正 $x$ 边形,则任意 $x$ 的约数都已经被选择。

那么现在考虑加入正 $x$ 边形后,对答案有多少贡献。容易发现的是,由于 $x$ 所有约数都已经选入,所以对于原本正 $x$ 边形应该有的 $x$ 个交点的贡献,其中那些能被 $x$ 的约数贡献的点都需要去除。显然剩下的点的个数是 $\varphi(x)$。则按照 $\varphi(x)$ 从小到大贪心地加入即可。

由于没有正 $2$ 边形,所以需要特判一下。

时间复杂度 $\mathcal{O}(n\log n)$。

标签: 数论, 贪心

添加新评论