首先洛谷的题面十分的劝退(至少对我这个菜鸡来说是这样)，我来解释一下(原来的英文题面)：
有一个有若干个密码(每个密码都可以开箱子)的密码箱，密码是在$0$到$n-1$的数中的，且所有的密码都满足一个条件：如果$x$是密码，$y$也是密码($x$可能等于$y$)，那么$(x+y)\%n$也是密码。现在有一个人在试密码，他试了$k$个数，前$k-1$个都是错的，第$k$个是对的。现在你要求这个密码箱最多有多少不同的密码。
显然如果$x$是一个密码，那么$ax(a∈N&&ax<n)$也都是密码。根据裴蜀定理，我们先让$num_k$和$n$取一个gcd得到$g$，然后把$g$分解因数得到$fac$个因数。从小到大枚举因数$f$，如果对于一个因数$f$前$k-1$个数都不能整除它，说明它符合题意，这个时候答案就是$frac{n}{f}$，也就是取它的所有倍数。
然后我们发现这个玩意直接枚举来做的话理论上最差是$O(sqrt(n)k)$的，看起来根本过不去(实际上可以水过去)，于是学习了一种筛法的解法。
我们换一种方法检查每个因数是否合法：首先标记$i=1->k-1$中所有的$gcd(num_i,num_k)$为不可取。接下来要用到一个性质：如果一个数$x$不可取，那么$x$所有的因数也一定都不可取(不要搞反了)。这样我们从大到小枚举一下$num_k$的所有因数$fac_i$，每次从小到大枚举$num_k$的质因数$pfac_j$，每次查看$num'=fac_i*pfac_j$(如果这个数存在的话)，如果它不可取就将当前的因数标记为不可取，最后正着扫一遍就行了。复杂度$O(fac$ $log(n)log(fac))$(根本跑不满)
Update：讲了以后收到了很多疑问，筛答案那块没啥问题，主要是证明“显然如果$x$是一个密码，那么$ax(a∈N&&ax<n)$也都是密码” 这里(根本不显然=。=)和“根据裴蜀定理，我们先让$num_k$和$n$取一个gcd” 这里(为什么取gcd=。=？)。发现自己根本讲不清楚(完全暴露了数学鶸的本质233)，看来还是要提高一个知识水平orz
现在更新一下详细证明：
1.为什么“如果$x$是一个密码，那么$ax(a∈N&&ax<n)$也都是密码”
这个问题有一个更“朴实”的问法：凭什么你可以用一个$x$和它的所有倍数表示出答案，而不是两个数组合呢？
(讲的时候极尬，完全不会讲TAT)
我们首先证明一个东西：如果$x$是密码，$y$是密码，那么$gcd(x,y)$也是密码
这个东西可以由裴蜀定理得出，问题是裴蜀定理说的是整数，我们要求必须是正整数
不过没关系，因为我们在模$n$剩余系下做，所以我们想$-ax$就等价于$+(kn-a)x(a,k∈N*)$
证明了这个，那么所有“两个数的组合”就都可以表示成它们的$gcd$了，于是问题解决
2.为什么“先让$num_k$和$n$取一个gcd”
暴力做应该不用取，但是筛的时候必须取
首先裴蜀定理告诉我们这样做了之后还是对的
那么为什么必须这样做呢？因为$num_k$中可能还有一个(相对于前$k-1$个数)独特的因数，然后你在排除的时候这个因数根本排不掉，你就把它当成答案了。。。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int N=500005; 6 long long p[N],fac[N],pfac[N]; 7 long long n,k,g,tot,cnt; 8 bool una[N]; 9 long long gcd(long long a,long long b) 10 { 11 return b?gcd(b,a%b):a; 12 } 13 void getf(long long maxx) 14 { 15 for(long long i=1;i*i<=maxx;i++) 16 if(maxx%i==0) 17 { 18 fac[++tot]=i; 19 if(i*i!=maxx) 20 fac[++tot]=maxx/i; 21 } 22 } 23 void getpf(long long maxx) 24 { 25 for(long long i=2;i*i<=maxx;i++) 26 if(maxx%i==0) 27 { 28 pfac[++cnt]=i; 29 while(maxx%i==0) maxx/=i; 30 } 31 if(maxx!=1) pfac[++cnt]=maxx; 32 } 33 int main() 34 { 35 scanf("%lld%lld",&n,&k); 36 for(int i=1;i<=k;i++) 37 scanf("%lld",&p[i]); 38 if(!p[k]&&k==1) printf("%lld",n),exit(0); 39 p[k]=gcd(p[k],n),getf(p[k]),getpf(p[k]); 40 sort(fac+1,fac+1+tot); 41 for(int i=1;i<k;i++) 42 una[lower_bound(fac+1,fac+1+tot,gcd(p[i],p[k]))-fac]=true; 43 for(int i=tot;i;i--) 44 if(!una[i]) 45 for(int j=1;j<=cnt&&fac[i]*pfac[j]<=n;j++) 46 { 47 long long tmp=fac[i]*pfac[j]; 48 int pos=lower_bound(fac+1,fac+1+tot,tmp)-fac; 49 if(fac[pos]==tmp&&una[pos]) {una[i]=true; break;} 50 } 51 for(int i=1;i<=tot;i++) 52 if(!una[i]) {printf("%lld",n/fac[i]); break;} 53 return 0; 54 }