题面大意
在一个圆上有 N 个间隔相等的点,依次编号为 0,1,\dots,N−1,Alice 在点 0 处,Bob 在点 K 处。
初始时,所有点的颜色都是白色。从 Alice 开始,他们交替执行以下操作:
- 选择当前白色点中的一个点,将其染成黑色。操作完成后,各点的颜色必须与连接操作者和圆心的直线对称。
如果操作符无法执行满足上述条件的操作,则操作序列就此结束。双方合作并做出最佳选择,使最后被涂成黑色的点的总数达到最大。
确定操作序列结束时是否所有点都被染成黑色,是则输出 Yes
,不是则输出 No
。
思路
以下所有点的编号对 N 取模。
当第一个染色点确定时,两人的每一步操作都是确定的:Alice 第一步染点 x,Bob 第二步只能染 x 关于点 K 的对称点……
而在对称的过程中,如果 Bob 上一次染了点 x,则 Alice 这一轮会染点 -x;如果 Alice 上一次染了点 x,则 Bob 这一轮会染点 2K-x。
而如果 Alice 第一步绘制的是点 0,那么两人的染色顺序将是:
0,2B,-2B,4B,-4B,\dots
这种情况一直持续到所有与 0 距离为 \gcd(N,2K) 的点全部染色为止。如果 N 为偶数且 Alice 第一步绘制的是点 \frac{N}{2},最终的染色序列也是一样的。此时整个圆在 Alice 和 Bob 看来都是对称的。
此时考虑已经被染色的点数 X=\frac{N}{\gcd(N,2K)}:
若 X 是奇数,则此时轮到 Bob 染色。容易知道此时点 K 一定被染色了。
- 如果在给出的点中并没有点 K 的对径点(即 N 为奇数),Bob 将无法操作。此时如果 \gcd(N,2K)=1,则已经染色完成,否则无法全部染色。
- 否则,N 为偶数,此时点 K 的对径点一定尚未染色。Bob 可以将点 K 的对径点染色,然后开启新一轮操作,对 X 个点进行染色,往后将无法进行任何染色操作。此时如果 2X=N,即 \gcd(N,2K)=2,则已经全部染色,否则复发全部染色。
若 X 是偶数,则此时轮到 Alice 染色。容易知道 N 为偶数且点 0 的对径点已经染色,Alice 无法继续染色。而此时 \gcd(N,2K) 至少是 2,所有点并没有全部染色,也无法全部染色。
综上,可以全部染色的条件为一下两者之一:
直接判断输出即可,代码就不放了。