题目描述
有一个密码箱，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 分析： （1）假设 x 是密码 ， 那么 (x+x)%n = 2x%n 也是密码，则有 (2x%n+x)%n = 3x%n 也是密码，由此可得，对于任意正整数 m，如果 x 是密码，那么 mx%n 是密码 mx%n 是密码的意思就是 mx-nc = 密码 = gcd（x,n）->由拓展欧几里得可得 （2）假设x和y是密码，那么（x+y）%n 也是密码，同上，则有 ax + by = gcd(x,y)
对于任何一个密码集A，分析：
设 A中所有的数的GCD为 e由以上两个可知 e ∈ A如果集合 A中有比 e更小的密码q，则 GCD(e,q) < e ,不符合分析1中的设定，所以 e 是 A中的最小的数所以 A 中所有的数为 x，2x，3x，4x … #include <cstdio> #include <algorithm> using namespace std; long long a[250010]; long long q[250010]; bool f[1300000]; long long gcd(long long i,long long j){ return j? gcd(j,i%j):i; } int main(){ long long n;int k; while(scanf("%I64d%d",&n,&k)){ //将1-(k-1)个错误解和第k个解输入数组 for(int i=1;i<=k;i++) scanf("%I64d",&a[i]); //接下来求正解和n的最大公约数 long long gg = gcd(n,a[k]); //12 //找到密码的因数 long long cnt = 0; for(long long i=1;i*i<=a[k];i++) { if(a[k]%i==0){ q[++cnt]=i; if(i*i!=a[k]) q[++cnt]=a[k]/i; } } //将因数排序 sort(q+1,q+cnt+1); for(int i=1;i<k;i++) a[i]=gcd(a[i],a[k]); // f数组中存储的是错误密码的因子 // lower_bound函数目的是找到错误因子在q数组中的地址 - 首地址就是第几个 for(int i=1;i<k;i++){ f[lower_bound(q+1,q+cnt+1,a[i])-q]=1; } for(int i=1;i<=cnt;i++){ if(f[i]){ for(int j=1;j<i;j++) if(q[i]%q[j]==0) f[j]=1; } } long long ans; for(ans=1;f[ans];ans++); printf("%d\n",n/q[ans]); return 0; } }