删除最少数量的刀片

Question

最近,我在Timus在线评委中遇到了这个问题.对于不愿点击链接的人.问题如下:

乌拉尔锦标赛的经验丰富的参与者提前来到叶卡捷琳堡,以适应恶劣的天气条件,在城市中漫步,当然,还可以参观"林波波"水上公园.没有多少人知道水上乐园附近有404号植物,这个植物被当地人称为"错误404".这个工厂确实不容易找到,而且要了解那里发生的事情仍然更加困难.幸运的是,人们可以从附近的人行天桥上观看植物.由于植物看似静止和苍凉,人们可能会认为它已经停止运转,但事实并非如此.该工厂的主要工作区域是航空发动机的维修.不久前,该工厂收到了修理损坏的燃气涡轮发动机的命令.事实证明,一些叶片被撕掉,导致发动机轴上的负载过大.该工厂的专家已经决定,通过移除一些完整的叶片可以快速修复发动机,使剩余叶片的质量中心再次位于旋转轴上.为了使发动机功率尽可能大,应移除最少数量的叶片.必须留下至少一个叶片,否则发动机根本不起作用.专家断言,当所有叶片完好无损时,它们的端点形成一个正常的n-gon.告诉他们应该拆除哪些刀片.

> Input The first line contains the initial number of blades in the
> turbine n and the number of torn blades k (3 ? n ? 20000; 1 ? k ? n ?
> 1). The integer n has at most two distinct prime divisors. The next
> line contains k integers, which are the numbers of the torn blades in
> ascending order. The blades are numbered from 1 to n clockwise. 
Output
> In the first line output the minimum number of blades that should be
> removed. In the second line output the numbers of these blades in any
> order separated with a space. If several answers are possible, output
> any of them. If it is impossible to repair the engine by removing some
> of the blades, output “?1”. 
> 

我在设置此问题时遇到问题.我最初的想法是,由于需要恢复质心,因此需要将破碎的刀片包围在相同数量的未破碎刀片上.

因此,如果我们将损坏的刀片表示为0并且将完整的刀片表示为1,则特定配置可表示为:011

我不确定自己是否走在正确的轨道上并且在尝试理解这个问题时会有一些反馈意见.

谢谢

Answer 1

我最初的想法是，由于需要恢复质心，因此破损的刀片需要被相同数量的未破损的刀片包围。

不可以。螺旋桨必须是旋转对称的。如果 3 叶片螺旋桨的一个叶片折断，则无法将其重新调整到中心位置。

关键点是：

1. 专家断言，当所有叶片都完好无损时，它们的端点形成了规则的多边形。

2. 整数 n 至多有两个不同的素因数。

从适合这两个属性的简单事物开始，例如十边形。问问自己：多边形和对称性有何关系？10 的约数与多边形和对称性有何关系？为了简化事情，您可以使用标量而不是二维点来表示这些多边形吗？提示：模块化算术参与解决方案。

刀片配置的图片（未固定和固定）应该会有所帮助。例如：

        2 2 2 2           
    3 1 1                                                 
  4 0 4 0 4 0 4 0     

  5 9 5 9 5 9     
    6 8 6 8 6 8 8       
        7 7 7 7           
   整个 10 边形 2 个破碎刀片 3 个破碎刀片 3 个破碎刀片

对于 2 个损坏的刀片和前 3 个损坏的刀片，有两种可能的解决方案，但每种解决方案只有一种是最佳的。第二个3-broken有一个解决方案。寻找多边形。