题目大意：给定n和k个整数，求mod n加法下的群G的一个子群G'，满足a[1]~a[k-1]都不在群中而a[k]在群中

首先易证G'一定是一个循环群

证明：显然若a在群中则a的逆元在群中

那么我们就有了减法运算

由群的封闭性可得若a和b都在群中则gcd(a,b)一定在群中

不妨设g为G'中所有元素的gcd 那么群G''={0,g,2g,...}一定是G'的一个子群

由于G'-G''中的所有元素均不是g的倍数，故G'∩(G'-G'')为空 G'=G''

由此可得G'是以g为最小生成元的一个循环子群 大小为n/g

上面都是废话

总之我们现在就要找到一个数g，使得g|n且g|a[k]，且对于任意1<=i<=k-1，g不是a[i]的约数

这个MS没有什么办法直接做

我们发现10^14以内的数约数个数最多只有17280个

因此我们将a[1]~a[k-1]中所有的数对n取gcd，排序去重，这样k的规模就减小到了17280

然后枚举gcd(n,a[k])的所有约数，暴力验证，取最小的g就是结果

时间复杂度O(√n+klogn+17280^2)

卡爆了

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #define M 250250 using namespace std; int k,tot; long long n,ans,a[M]; void Check(long long x) { int i; for(i=1;i<=tot;i++) if(a[i]%x==0) return ; ans=min(ans,x); } int main() { int i; cin>>n>>k;ans=n; for(i=1;i<=k;i++) { #ifdef ONLINE_JUDGE scanf("%lld",&a[i]); #else scanf("%I64d",&a[i]); #endif a[i]=__gcd(n,a[i]); } sort(a+1,a+k); for(i=1;i