P2579 - 例1.1-2 密码

内存限制：128 MB 时间限制：1.000 S

评测方式：文本比较命题人：

提交：2 解决：1

有一个密码箱，0到$n$-1中的某些整数是它的密码。且满足：如果$a$和$b$都是它的密码，那么（$a+b$）％$n$也是它的密码（$a,b$可以相等，％表示整除取余数，下同），某人试了$k$次密码，前$k$-1次都失败了，最后一次成功了。

问：该密码箱最多有多少不同的密码。

输入第一行两个整数分别表示$n,k$

第二行为$k$个用空格隔开的非负整数，表示每次试的密码。

数据保证存在合法解。

输出一行一个数，表示结果

42 5
28 31 10 38 24

## 数据范围

- 对于10%的数据：$N≤10^4，k≤100$
- 另有10%的数据：$N≤10^9，k≤100$
- 另有10%的数据：$N≤10^9，k=1$
- 对于前60%的数据：$k≤1000$
- 对于100%的数据：$1≤k≤250000，k≤n≤10^14$

2579: 例1.1-2 密码