P4296 [AHOI2007]密码箱

(x)是密码，(gcd(x,n))也是密码 证明显然

(x)和(y)是密码，(gcd(x,y))也是密码

证明：设(x,y)是密码，((px+qy)\%n)也是密码 (ax+by=gcd(x,y))有解

所以(ax+byequivgcd(x,y)(mod~n))有解

因为(ax+byequiv ax+by+pnx+qnx(mod~n))

即((a+pn)*x+(b+qn)*yequivgcd(x,y))一定有解

进而(gcd(x,y))是密码

令(l=gcd(a[k],n))，处理出(l)所有因子，筛去因子为(gcd(l,不是密码的数))的因子，根据结论2，这些因子不是密码，找出最小的因子，输出(n/k)

ll a[N],q[N<<1],f[N<<1],i,j,ans,tot,n,k;
int main(){
    n = read(); k = read();
    for(i = 1;i <= k;++i)
    	a[i] = read();
    a[k] = __gcd(a[k],n);
    for(i = 1;i < k;++i)
    	a[i] = __gcd(a[i],a[k]);
    for(i = 1;i * i <= a[k];++i)
    	if(a[k] % i == 0){
        	q[++tot] = i;
        	if(i * i != a[k]) q[++tot] = a[k]/i;
    } 
    sort(q + 1,q + tot + 1);
    for(i = 1;i < k;++i)
    	f[lower_bound(q + 1,q + tot + 1,a[i]) - q] = 1;
    for(i = 1;i <= tot;++i)
     	if(f[i])
      		for(j = 1;j < i;++j)
       			if(q[i] % q[j] == 0)
        			f[j] = 1;
    for(ans = 1;f[ans];++ans);
     	write(n/q[ans]);
}