密码
题目描述
有一个密码箱,0到n-1中的某些整数是它的密码。且满足:如果a和b都是它的密码,那么(a+b)%n也是它的密码(a,b可以相等,%表示整除取余数),某人试了k次密码,前k-1次都失败了,最后一次成功了。
问:该密码箱最多有多少不同的密码。
输入
第一行两个整数分别表示n,k(1≤k≤250000,k≤n≤1014)。第二行为k个用空格隔开的非负整数,表示每次试的密码。数据保证存在合法解。
输出
输出一行一个数,表示结果。
样例输入
42 5
28 31 10 38 24
样例输出
14
数据规模
对于10%的数据:N≤10^4,k≤100;
另有10%的数据:N≤10^9,k≤100;
另有10%的数据:N≤10^9,k=1;
对于60%的数据:k≤1000;
对于100%的数据:1≤k≤250,k≤n≤10^14;
信息
- 难度
- 9
- 分类
- (无)
- 标签
- 递交数
- 2
- 已通过
- 1
- 通过率
- 50%
- 上传者