首先 我们把盒子看做一个集合$A$，来研究一下这个集合的性质。为了方便，我们把$0$看做$n$。

显然若$x\in A$则$\forall k \in Z,kx \:mod \: n \in A$。

根据裴蜀定理,$\forall \gcd(x,n) | k , k \in A$。

以及若$x,y \in A$则$\gcd(x,y) \in A$。

对于每个不能选的$x$，要满足$\gcd(x,n) \notin A$根据这一点我们可以在$O(\sqrt{n}log{n})$的复杂度内求出所有不能被放进去的$n$的因数。

具体地，采用记忆化搜索，对于每一个确定不能选的$x$，枚举其所有可能的质因数$($在$1e14$范围内最多$13$个$)$，并继续向下搜。记不能选的集合为$B$。

剩下的部分我们可以选择一些作为一开始在$A$中的数，剩下的由这些数组合出来。可以证明，只会选择一个这样的数:

若同时选择$x,y$，且$x,y$非倍数关系: 若$\gcd(x,y) \in B$，则根据上文，$x,y$一定不能同时出现。 否则，$\gcd(x,y)$一定可以把$x,y$能表示的都表示出来，故选择$\gcd(x,y)$而非$x,y$。

对于要选的$x$，要满足$\gcd(x,n) \in A$。设上文选择的数为$a$，则有$a|\gcd(x,n)$，$Ans=\frac{n}{a}$。$a$最多有$O(\sqrt{n})$种取值，枚举即可。

代码比较丑，仅供参考。

#include<bits/stdc++.h>
#define int long long 
using namespace std;
int n,m;
int X[301000];
const int N=1e7,E=1e4;
bitset<N+E>pvis;
int pri[N/10+E],ptot;
int np[55],ntt;
bitset<2*N+E>vis;
unordered_map<int,int>mp;
int ans;
void solve(int x){
	vis[mp[x]]=1;
	for(int i=1;i<=ntt;i++){
		if(x%np[i]==0){
			int y=x/np[i];
			if(vis[mp[y]]==0) solve(y);
		}
	}
}
int Phi(int x){
	int ret=x;
	for(int i=1;i<=ntt;i++){
		if(x%np[i]==0){
			ret=ret/np[i]*(np[i]-1);
		}
	}return ret;
}
signed main() {
	for(int i=2;i<=N;i++){
		if(pvis[i]==0) pri[++ptot]=i;
		for(int j=1;j<=ptot&&i*pri[j]<=N;j++){
			pvis[i*pri[j]]=1;
			if(i%pri[j]==0) break;
		}
	}
	ios::sync_with_stdio(0);
	cin.tie(0);
//	freopen("ex.in","r",stdin);
//	freopen("my.out","w",stdout);
//	system("fc ex.out my.out");return 0;
	cin>>n;ans=0;
	int stt=0;
	for(int i=1;i<=sqrt(n);i++){
		if(n%i==0){
			mp[i]=++stt;
			if(i*i!=n) mp[n/i]=++stt;
		}
	}
	int nn=n,ed=0;
	for(int i=1;pri[i]<=sqrt(n)&&i<=ptot;i++){
		if(n%pri[i]==0){
			np[++ntt]=pri[i];
			while(n%pri[i]==0) n/=pri[i];
		}
	}if(n>1) np[++ntt]=n;
	n=nn;
	cin>>m;
	for(int i=1;i<=m;i++){
		int x;cin>>x;if(x==0) x=n;
		if(i!=m){
			x=__gcd(n,x);
			if(vis[mp[x]]) continue;
			solve(x);
		}else{
			ed=x;
			ed=__gcd(ed,n);
		}
	}
	stt=0;
	for(int i=1;i<=sqrt(n);i++){
		if(n%i==0){
			stt++;
			if(ed%i==0){
				if(vis[stt]==0) ans=max(ans,n/i);
			}
			if(i*i!=n){
				stt++;
				int ip=n/i;
				if(ed%ip==0){
					if(vis[stt]==0) ans=max(ans,i);
				}
			}
		}
	}
	
	cout<<ans;
	return 0;
}

洛谷P3518 [POI 2011] SEJ-Strongbox