luogu P3518 [POI2011]SEJ-Strongbox | loj #2160. 「POI2011 R2 Day0」保险箱 Strongbox

代码已在 loj 上不开 O2 通过。

下文均在 \(Z_n\) 下考虑。

首先，你考虑选出一些数，能组成的数。即 ttps://www.cnblogs.com/xugangfan/p/17040634.html

那么对于一个不在群里的数 \(x\)，若有 \(d\)，满足 \(d|x\)，则 \(d\) 显然不在群里。又因为在 \(Z_n\) 下，所以 \(\gcd(d,n)\) 也不在群里。

接着，你考虑答案是若干个数以及 \(n\) 的线性组合，这些数的 \(\gcd|n\)，因此，考虑确定他们的 \(\gcd\) 这样我们就确定了可选的数以及生成的群 \(\langle \gcd\rangle\)。又因为你要让群的元素数量最大，根据 \(\langle d\rangle=n/d,d|x\)，我需要让 \(\gcd\) 最小，那么能够选择的元素即为 \(\sum_i [\gcd|i]\)。

考虑枚举这个 \(\gcd\)，那么对 \(n\) 分解因数可得到，然后你需要满足 \(\gcd | a_k\)，且 \(\forall i\in [1,k-1],\gcd \not | a_i\)，注意前者是可以直接干掉的，后者可以对 \(n\) 进行质因数分解，然后 \(\forall i\in [1,k-1]\) 都与 \(n\) 取 \(\gcd\)，然后变成了一个高维后缀 or，你直接做就是对的，hash 一下用 map 存即可。

#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
const int N=(int)(3e5+5),mod=998244353;
mt19937 RAND(time(0));
const int base=RAND()%mod;
map<int,bool>mp;
int n,k,a[N],vec[N],tot,o[N],ct,v[100],mxv[100],ID;

int gcd(int x,int y) {
	return !y?x:gcd(y,x%y);
}

void add() {
	int res=0;
	for(int i=1;i<=ct;i++) res=(res*base%mod+v[i])%mod;
	res=(res%mod+mod)%mod;
	mp[res]=1;
}

void dfs(int st) {
//	cout<<st<<'\n';
	if(st==ct+1) {
		int res=0;
		for(int i=1;i<=ct;i++) res=(res*base%mod+v[i])%mod;
		res=(res%mod+mod)%mod;
		int res2=0;
		for(int i=1;i<=ct;i++) {
			if(i==ID) res2=(res2*base%mod+(v[i]+1))%mod;
			else res2=(res2*base%mod+v[i])%mod;
//			cout<<v[i]<<' ';
		}
//		cout<<'\n';
		res2=(res2%mod+mod)%mod;
		mp[res]|=mp[res2];
		return ;
	}
	for(int i=mxv[st];i>=0;i--) {
		v[st]=i; dfs(st+1);
	}
}

void init() {
	int x=n;
	for(int i=2;i*i<=x;i++) {
		if(x%i) continue ;
		o[++ct]=i;
		while(x%i==0) x/=i,++mxv[ct];
	}
	if(x!=1) o[++ct]=x,mxv[ct]=1;
	for(int i=1;i<k;i++) {
		a[i]=gcd(a[i],n);
		x=a[i];
		for(int j=1;j<=ct;j++) {
			v[j]=0;
			if(x%o[j]) continue ;
//			int qwq=0;
			while(x%o[j]==0) v[j]++,x/=o[j];
		}
		add();
	}
	for(int i=1;i<=ct;i++) {
		ID=i; dfs(1);
	}
}

bool chk(int x) {
	for(int i=1;i<=ct;i++) {
		v[i]=0;
		if(x%o[i]) continue ;
		while(x%o[i]==0) v[i]++,x/=o[i];
	}
	int res=0;
	for(int i=1;i<=ct;i++) res=(res*base%mod+v[i])%mod;
	res=(res%mod+mod)%mod;
	return mp[res];
}

signed main() {
//	freopen("2.in","r",stdin);
	cin.tie(0); ios::sync_with_stdio(false);
	cin>>n>>k;
	for(int i=1;i<=k;i++) cin>>a[i];
	init();
	int D=n;
	int ans=0;
	if(!a[k]) {
		for(int i=1;i*i<=n;i++) {
			if(n%i) continue ;
			if(!chk(i)) {
				D=min(D,i);
				break ;
			}
			if(!chk(n/i)) vec[++tot]=n/i;
		}
		if(D==n) {
			for(int i=tot;i>=1;i--) {
				if(!chk(vec[i])) {
					D=min(D,vec[i]);
					break ;
				}
			}
		}
	} else {
		for(int i=1;i*i<=n;i++) {
			if(n%i) continue ;
//			int qwq=__gcd(n,a[k]);
			if(a[k]%i==0&&!chk(i)) {
				D=min(D,i);
				break ;
			}
//			qwq=__gcd(n,a[k]/i);
			if((a[k]%(n/i)==0)) vec[++tot]=n/i;
		}
		if(D==n) {
			for(int i=tot;i>=1;i--) {
				if(!chk(vec[i])) {
					D=min(D,vec[i]);
					break ;
				}
			}
		}
	}
	cout<<n/D;
	return 0;
}