【题解】CF1208G Polygons

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)$。