Skip to content

11293: 【原1293】Black King Bar

题目

题目描述

author: Xihu Zhang 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1293

Description

Black Yellow Bar!

Yellow哥有根BKB,但他只是用来修机房电风扇。

在Yellow哥还不那么出名的时候,他顶着艰苦的环境在一家“5毛一小时”的网吧里刷TC。网吧里没有空调。只有电扇,而且电扇的叶片也脱落了不少,电扇长这个样子:

1293

当电扇吊在屋顶上时,如果电扇的有扇叶脱落,可能导致电扇不平衡。会歪向一边。

这家网吧的电扇也很特别,它总共有N个等分叶片,任意两个叶片间隔相等,大小距离相同,而且N满足N=P^a*Q^b,其中P、Q为质数,a,b为非负整数。

Yellow哥不喜欢歪向一边的电扇。因为这样会使得患有强迫症的他刷题速度降低。

所以Yellow哥会用BKB拆掉几片扇叶来恢复电扇的平衡。图中的电扇是平衡的。它的重心在其中心。

Yellow哥想拆掉最少的叶片使得电扇恢复平衡。

现在给出一电扇的状态,电扇的叶片顺次从1到N标号,其中有M个叶片脱落。求最少要拆掉多少叶片才能让电扇恢复平衡。

Input Format

第一行两个数字N、M

接下来M行,每行一个数字,表示电扇脱落的叶片编号,按升序给出。

Output Format

一个数字,表示为使电风扇平衡所需要拆掉的叶片的最少数量。

Sample Input

12 5
1
4
5
9
10

Sample Output

0

Sample Illustration

样例给出的风扇如题面中的图片所示,由于一开始就是平衡的,所以不需要拆掉任何扇叶。至于为什么平衡……物理分析分析吧。

Hint

30%的数据:1≤N≤10。

50%的数据:1≤N≤10000。

100%的数据:1≤N≤2*10^6,M≤N,编号为1到N中的数字。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!