蛋糕

试试 5 刀能把一个蛋糕切成几块

你傻啊,又没让你直着切。。。

题目大意

正 $n$ 边形边长为 $1$,求最小的正 $m$ 边形的边长,使得该正 $m$ 边形能在中心共点时,完全覆盖正 $n$ 边形。

其中 $n,m\le 10^9$。

题解

啥啊。

不会啊。

那我们先来乱 bb 一下。

猜测

我们可以大胆断言,正 $m$ 边形的内切圆和正 $n$ 边形的外切圆重合。

肯定是错的。

随便就能举例啊,像什么正三角形包正六边形,对吧。

那该怎么办呢?

我们可以发现,这样构造出来的答案一定比标答要大,问题是怎么把现在的答案变小。

意思就是要从内切-外接圆模型开始,通过一定的变化,在保证合法的前提下使得答案变小。

当然在这里我是把题转换成了求里面那个多边形边长的最大值来做的,这样我觉得更好理解。

我们考虑题目的限制要求说明了什么。

两个多边形中心共点

想来大家都能用顶点与中心的连线来表示正多边形。那么我们考虑对于任意放置的两组连线,对应的答案为:

$$
\min\left\{|OP_i|\right\}
$$

如何得到另一种答案呢?

是不是旋转那组射线?

是不是感觉有点思路了?

但是转动的角度没法枚举啊。

那我们就直接考虑什么时候它是最大的吧。

等等。

最小值最大?

emmm.

二分?

二分

二分一下最短的那条 $OP_i$ 是多长,对于每一条对角线验证是否可行。

直接算与最近的中心到边的垂线段(以下简称中心距)的夹角,然后比较大小即可。

记得算算最短的那条的夹角。

即为上图中的 $\alpha$ 和 $\beta$。

可以发现 $\alpha$ 即为旋转角。

这样的话时间复杂度为 $\mathcal O\left(n\log{\cfrac{1}{eps}}\right)$ 左右,会 T 成傻逼。

旋转角

能不能不要二分,直接根据 $n,m$ 算出 $\alpha$?

诶这个是可以的。

我们考虑一下,现在最短的边是 $OP_1$,我们只需要找到第二短的 $OP_i$ 然后旋转使它们相等就行了。

因为这样再往后转和往前转是等效的,最小值只会减小。

吗?

这不一定吧。

比如这样:

如果我们假设 $|OP_3|\lt |OP_2|$,那么在 $OP_1$ 顺时针旋转的过程中,$|OP_3|$ 是会变大的。

emmm.

完了。

不会了。

似乎只有向着中心距运动的才会变小?

而且第二长的有可能是另一个与中心距重合的射线。

那么显然的,这里需要对每一个区间单独讨论,区间由与中心距重合的射线分割开来。

但是这样处理好像会有问题啊。

比如如果有一条射线在某一条中心与顶点连线上,这样旋转大于 $\cfrac{\pi}{2m}$ 后这条线可能会比 $OP_1$ 短。

我们来看看什么时候才会转到 $\cfrac{\pi}{2m}$。

选择角度

可以发现 $OP_1$ 的有效旋转角度为 $\left(\text{-}\cfrac{\pi}{m},\cfrac{\pi}{m}\right)$,因为再继续旋转,可以把整张图逆时针旋转 $\cfrac{2\pi}{m}$,这样和一开始是一样的。

并且由于第二短的那条边是和 $OP_1$ 相等了,所以它们与最近中心距的夹角为相反数,那么第二短的那条边与它的下一条中心距的夹角为现在的两倍,即旋转角的两倍。

第二短的边与下一条中心距的夹角大于 $\cfrac{\pi}{m}$。

那么我们举出来的那条的夹角又是多少呢?

是不是就是 $\cfrac{\pi}{m}$?

emmm.

所以它要想比 $OP_1$ 还短是不可能的。

这里还有另一种证明顺时针时选择下一条中心距合理的方法,可以先阅读对称后再来理解。

考虑对于每一个可能先增大后减小的 $|OP_i|$,一定有一条对应的 $OP_{j}$,初始长度等于 $|OP_{i}|$ 且向减小后增大。所以 $|OP_i|\ge|OP_j|\ge |OP_1|$。

每一条中心距可以表示为 $OP_1$ 在的那条中心距旋转 $k_1\cfrac{2\pi}{m}$,射线可以表示为 $OP_1$ 旋转 $k_2\cfrac{2\pi}{n}$ 度。

那么可以得到如下结论:

$$
\alpha=\min\limits_{0\lt k_1\lt m,0\le k_2\lt n,\\0\lt k_1\frac{2\pi}{m}- k_2\frac{2\pi}{n}\lt \frac{2\pi}{m},\\\forall x\le k_1,y\le k_2,x\frac{2\pi}{m}\ne y\frac{2\pi}{n}}\left\{\cfrac{k_1\cfrac{2\pi}{m}-k_2\cfrac{2\pi}{n}}{2}\right\}
$$

现在我们需要解决的就是这个式子。

化简角度

什么分子分母同时除以 $2$ 我就不说了。

我们来仔细的分析一下这个式子。

首先,$\forall$ 之后的全部都没用,因为只要满足第二行的条件,这一行只是 $k_1/k_2$ 加上 / 减去一个区间大小而已。

所以问题和关键在于 $k_1\cfrac{\pi}{m}- k_2\cfrac{\pi}{n}$。

设 $k_1\cfrac{\pi}{m}- k_2\cfrac{\pi}{n}=x\pi\ (0\lt x\lt\cfrac{1}{m})$,显然 $k_1n-k_2m=mnx$,因为 $n,m,k_1,k_2\in \mathbb{N}$,所以 $\gcd(n,m)\mid mnx$,所以 $mnx\ge \gcd(n,m)$。

而且这个解是一定可以构造出来的,可以想一想拓展欧几里得是用来干什么的,并且如果 $k_1\gt 0$,$k_1m$ 一定 $\ge \gcd(n,m)$,所以 $k_2\ge 0$。

由此可得:

$$
\alpha=\cfrac{\gcd(n,m)\pi}{nm}
$$

所以就完了?

其实不然。

可以发现这样只能是顺时针转的情况,还有逆时针的没有讨论。

逆时针与对称

能不能不讨论了?这样真的很麻烦。

其实是可以的。

我们考虑一下逆时针转的中心距选哪条。

是不是每条射线的上一条中心距?

是怎么表示的呢?

$$k_2\cfrac{2\pi}{n}-k_1\cfrac{2\pi}{m}$$

对吧。

写出这个式子,应该就能想到如何从顺时针转类推到逆时针转了。

直接轴对称一下,对称轴为平分两个相邻的分割区间的射线的角平分线所在直线。

我们还可以发现对称前后图形并没有改变,所以顺时针逆时针转是完全等效的,即有效的旋转角度其实是 $\left[0,\cfrac{\pi}{m}\right)$。

顺时针转的结论就完全足够了。

平面几何与三角函数

接下来的问题就需要来一点三角函数了。不过不用担心,只是一些基本的运用。

$
已知: OP_1=OP_2, OA=OB, OM\perp AB,|P_1P_2|=1,\\
\angle{P_1OP_2}=\cfrac{2\pi}{n},\angle{AOB}=\cfrac{2\pi}{m}\\
\angle{\alpha}=\cfrac{\gcd(n,m)\pi}{nm}\\
求: |AB|\\
解:\\
做\ ON\perp P_1P_2, 交\ P_1P_2\ 于点\ N\\
\because OP_1=OP_2, ON\perp P_1P_2\\
\therefore |NP_1|=\cfrac{1}{2}|P_1P_2|, \angle{NOP_1}=\cfrac{1}{2}\angle{P_1OP_2}\\
同理, 2|AM|=|AB|, \angle{AOM}=\cfrac{1}{2}\angle{AOB}\\
\because 在\ Rt\triangle ONP_1\ 中, \angle{ONP_1}=90^{\circ}\\
\therefore |OP_1|=\cfrac{|NP_1|}{\sin{\angle{NOP_1}}}\\
\because 在\ Rt\triangle MOP_1\ 中, \angle{OMP_1}=90^{\circ}\\
\therefore |OM|=|OP_1|\cos{\alpha}\\
\because 在\ Rt\triangle AMO\ 中, \angle{AMO}=90^{\circ}\\
\therefore |AM|=|OM|\tan{\angle{AOM}}\\
\begin{align*}
\therefore |AB| & =2|AM|\\
& =2|OM|tan{\angle{AOM}}\\
& =2|OP_1|\cos{\alpha}\tan{\cfrac{1}{2}\angle{AOB}}\\
& =2\cfrac{|NP_1|}{\sin{\angle{NOP_1}}}\cos{\alpha}\tan{\cfrac{\pi}{m}}\\
& =2\cfrac{\cfrac{1}{2}|P_1P_2|}{\sin{\cfrac{1}{2}\angle{P_1OP_2}}}\cos{\alpha}\tan{\cfrac{\pi}{m}}\\
& =\cos{\cfrac{\gcd(n,m)\pi}{nm}}\tan{\cfrac{\pi}{m}}\csc{\cfrac{\pi}{n}}
\end{align*}
$

小小地复习了一下解答过程该怎么写。

总之这道题到这里就完结了,但是还有一些可以写的东西。

骗分

来让我们好好研究一下如何骗分。

这道题的 $eps$ 只有 $10^{\text{-}4}$,所以如果 $\cfrac{\gcd(n,m)}{nm}$ 较小,可以发现 $\alpha$ 可以忽略不计,直接内切-外接圆就行了。

然后呢可以特判一些比如 $n\mid m$ 或 $m\mid n$ 的情况。

这样可以骗到 $80$ 分。

emmm.

这数据是有点水。

那么特判该怎么解决呢?

推荐形中有形这篇论文,我觉得写得很好,虽然给出的方法是 $\mathcal O(n)$ 的。

$m\mid n$

可以发现,一定有一些边是贴在一起的,比如最开始的那个 “三包六”。

那么两个多边形的内切圆相等。

直接搞就可以了。

$n\mid m$

自己画一画,嗯,相隔几个点连起来就可以了。

两个多边形的外接圆相同。

照样直接搞。

时间复杂度 $\mathcal O(1)$。

杨爷爷的另一种思路

这个思路是由 FirstLast 提供的。

可以发现一定有一个顶点重合或一条边平行。

为什么呢?

这样想说实话有点复杂了,它的本质是很简单的。

我们是不是把两根射线转来和两根中心距的夹角相反了?

这两根中心距是有一根对称轴的对吧?

这两根射线也是有一根对称轴的对吧?

就是把两根中心距向相反的方向旋转了相等的角度。

所以这两个对称轴就是同一根。

而对称轴要么过顶点要么垂直平分一条边,所以可以得到这样的结论。

然后就是求最小的夹角了,分别是 $(2k_1+1)\cfrac{\pi}{m}-(2k_2+1)\cfrac{\pi}{n}$ 和 $(2k_1+1)\cfrac{\pi}{m}-(2k_2)\cfrac{\pi}{n}$,其中 $k_1,k_2\in\mathbb N$,角度取绝对值。

把这两个东西再取个最大,就是夹角了。其实这个夹角就是之前说的旋转角。

如何证明一定取 $\gcd(n,m)$ 呢?

能取到

首先 $n,m$ 的系数不可能同偶,对吧?有个 $2$ 得约掉。

所以就只剩 “奇 + 奇” 或 “偶 + 奇” 了,分别对应 “顶点重合” 和 “边平行”。

一定存在

参考拓展欧几里得

代码

说实话在给了公式的情况下我是不想贴代码的,再写一遍太麻烦了。

所以我就没贴。