
 222通过
 643提交
 题目提供者 洛谷
 评测方式 云端评测
 标签 数论,数学 最大公约数,gcd POI 2011 高性能
 难度 提高+/省选
 时空限制 1000ms / 128MB
最新讨论 显示
题目描述
Byteasar is a famous safecracker, who renounced his criminal activity and got into testing and certifying antiburglary devices.
He has just received a new kind of strongbox for tests: a combinatorial safe.
A combinatorial safe is something different from a combination safe, even though it is opened with a rotary dial.
The dial can be set in $n$ different positions, numbered from 0 to $n1$.
Setting the dial in some of these positions opens the safe, while in others it does not.
And here is the combinatorial property, from which the name comes from:
if $x$ and $y$ are opening positions, then so is $(x+y)\ mod\ n$ too; note that is holds for $x=y$ as well.
Byteasar tried $k$ different positions of the dial: $m_1,m_2,\cdots,m_k$.
The positions $m_1,m_2,\cdots,m_{k1}$ did not open the safe,only the last position $m_k$ did.
Byteasar is already tired from checking these $k$ positions and has thus absolutely no intention of trying the remaining ones.
He would like to know however, based on what he already knows about the positions he tried, what is the maximum possible number of positions that open the safe.
Help him by writing an appropriate program!
给定n和k个整数，求mod n加法下的群G的一个子群G'，满足a[1]~a[k1]都不在群中而a[k]在群中
输入输出格式
输入格式：The first line of the standard input gives two integers $n$ and $k$, separated by a single space, $1\le k\le 250\ 000$, $k\le n\le 10^{14}$.
The second line holds $k$ different integers, also separated by single spaces, $m_1,m_2,\cdots,m_k$, $0\le m_i<n$.
You can assume that the input data correspond to a certain combinatorial safe that complies with the description above.
In tests worth approximately 70% of the points it holds that $k\le 1\ 000$.
In some of those tests, worth approximately 20% of the points, the following conditions hold in addition: $n\le 10^8$ and $k\le 100$.
输出格式：Your program should print out to the first and only line of the standard output a single integer: the maximum number of the dial's positions that can open the safe.
输入输出样例
说明
给定n和k个整数，求mod n加法下的群G的一个子群G'，满足a[1]~a[k1]都不在群中而a[k]在群中