ural1765解题报告.pdf

Error 404 题目描述 一个有 N 个刀片的涡轮，现在有一些刀片坏掉了，要求你在剩余的刀片中去掉最少的 刀片，使得最后涡轮的重心在中心的转轴上，例如： 左边为一个原本有 12 个刀片的涡轮，坏掉了一些刀片，我们将红色的2 个刀片部分去 掉后，剩下的图形重心在中心的转轴上。题目保证N ≤10000 ，且N 最多含有两个不同的 质因数。 问题分析 首先要解决的问题就是如：何判断一个涡轮的重心是否在中心转轴上。我们将所有的刀 片从0 到N-1 顺时针标号。那么容易可以知道，如果最后的图形有k 个刀片编号从小到大依 次为a , a a ，并且满足a a =+p且a (a =+p) mod N ; 那么这样的涡轮重心一定 1 2 k i i−1 1 k 在转轴上，例如： 除了这些图形之外，还有一些形式的涡轮的重心也在转轴，这些涡轮有什么特点呢？经 过观察可以得出，这些涡轮是有若干个上面那种形式的涡轮叠加而成的，例如样例： 我们可以将其分拆为红绿黄三个部分，每个部分都为上面的形式。因此我们可以得到一 个重要的结论：将最后剩余的刀片一定可以拆分成若干个形如：a , a a 的序列，其中 1 2 k ai ai−1 =+p 且a1 (ak =+p) mod N ; 这里我们不妨令所有的k 都是质数，因为若k 不是质数，那么我们可以找到k xy ， 那么可以将a , a a 继续拆分为：a , a , a a i ∈1, x 这 x 个序列。一直 1 2 k i i+x i+2 x + − ( [ ]) i y 1 x ( ) 拆分下去，最终k 将为一个质数。 根据ai ai−1 =+p 且a1 (ak =+p) mod N 可知：k * p N ，由于k 是个质数，且N 中 最多含有两个不同的质因数，因此k 的取值最多可能只有两种k ,k ； 1 2 N 可以枚举当k k1 所有可能的在最后答案中出现的a 序列，令p 为： k 1 0, p , 2p k −1 p ( 1 ) + + + − 1, 1 p , 1 2p 1 (k 1 1)p