问题描述：

有一个密码箱，0 到 n-1中的某些整数是它的密码，且满足：如果a和b都是它的密码，那么（a+b）%n

也是它的密码（a，b可以相等）某人试了k次密码，前k-1次都失败了，第k次成功了。

问：该密码箱最多有多少个密码？

输入输出：

输入第一行两个整数分别表示n，k。

第二行k个非负整数，表示每次试的密码。

输出一个数，为密码最多个数

分析

由题意，x是密码，那么（x+x）%n是密码，（2x+x）%n也是密码…… x*k%n是密码；①

x*k-n*c=GCD(x,n)

观察上面这个式子，一定有一个整数t，使得x*t%n==GCD（x，n）,由①可得，GCD（x，n）也是密码。

于是得出

结论1：如果x是密码，那么GCD(x，n)也是密码。

设x，y是两个密码，那么（p*x+q*y）%n也是密码。②

a*x+b*y=GCD(x,y)一定有解，所以a*x+b*y≡GCD(x,y) (mod n)一定有解③

因为：a*x+b*y ≡ a*x+b*y+p*n*x+q*n*x (mod n)

即 : （a+p*n）*x+(b+q*n)*y ≡ a*x+b*y (mod n) ④

由③④得：

(a+p*n)*x+(b+q*n)*y≡GCD(x,y)一定有解

由②得：(（a+p*n）*x+(b+q*n) )%n 一定是密码（a+p*n相当于②里面的p），

④=>a*x+b*y是密码 , 进而③=>GCD(x,y) 是密码。

于是得出

结论2：x，y是密码，那么GCD（x，y）也是密码

实现方法：

先设a[k]=GCD(n,a[k]),可以先在根号时间复杂度内处理出a[k]的所有因子，存在q数组中，

接着去除所有是GCD(a[i],a[k])的因数，设去除后最小的因子为x，那么答案是n/x。

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #define LL long long#define M 250005using namespace std;int f[M],k;LL a[M],q[M],n;LL gcd(LL a,LL b){    if(a