• Update on 2025.1.22：修订。

P3518 [POI2011] SEJ-Strongbox

若 $v$ 是密码，则所有 $\leq n$ 且是 $\gcd(v, n)$ 的倍数的数也是密码，因为 $kv \bmod n$ 取到了所有这样的数。

证明

设 $d = \gcd(v, n)$，$d\mid t$ 且 $t$ 不是密码，则 $kv \equiv t\pmod n$ 无解。根据裴蜀定理，它等价于 $\gcd(v, n) \nmid t$ 即 $d\nmid t$，矛盾。

进一步地，若 $u, v$ 是密码，则 $u' = \gcd(u, n)$ 和 $v' = \gcd(v, n)$ 是密码。由裴蜀定理，$\gcd(u', v')$ 在模 $n$ 意义下能被 $u'x + v'y$ 表出，所以 $\gcd(u', v')$ 是密码。

因此，设密码集合为 $S$，则 $d = \gcd(n, \gcd_{u\in S} u)\in S$。显然，$S$ 恰由 $d$ 的所有倍数组成。

考虑枚举这个 $d = \gcd(v, n)$，若合法则答案即 $\max\frac n d$，即我们需要找到最小的合法的 $d$。

设 $d_i = \gcd(m_i, n)$，$d$ 必须是密码与 $n$ 的 $\gcd$ 即 $d_k$ 的因数，其次任何 $d_i\ (1\leq i < k)$ 不能是 $d$ 的倍数。对于后者的限制，相当于在 $n$ 的所有因子形成的图上，一个点向它的因子连边，能被某个 $d_i$ 到达的因子是不合法的。

首先给所有 $d_i\ (1\leq i\leq k)$ 打上标记。从大到小枚举 $n$ 的每个因数 $c$，若 $c$ 被打上标记，则 $\frac{c}{p_j}$ 也应被打上标记，其中 $p_j$ 表示能整除 $c$ 的 $n$ 的质因子，表示若 $c$ 是某个 $d_i$ 的因数，则 $\frac c {p_j}$ 也是。

剩下没有被打标记的 $n$ 的因数 $d$，若 $d$ 能被 $d_k$ 整除则合法。找到最小的这样的 $d$，则答案为 $\frac n d$。

打标记的过程可以使用哈希表实现，时间复杂度 $\mathcal{O}(\sqrt n + k\log n + d(n)\omega(n))$，其中 $\omega(i)$ 表示 $i$ 的质因数个数。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

#define ll long long
inline ll read() {
	ll x = 0; char s = getchar();
	while(!isdigit(s)) s = getchar();
	while(isdigit(s)) x = x * 10 + s - '0', s = getchar();
	return x;
}

const int N = 2e4 + 5;
ll n, k, v, ans;
ll cpr, pr[N], cdv, dv[N];
void dfs(int p, ll v) { // dfs 找到所有 n 的因数
	if(p > cpr) return dv[++cdv] = v, void();
	dfs(p + 1, v);
	while(n / pr[p] >= v && n % (v *= pr[p]) == 0) dfs(p + 1, v);
}
void init() {
	ll x = n;
	for(ll i = 2; i * i <= x; i++)
		if(x % i == 0) {
			while(x % i == 0) x /= i;
			pr[++cpr] = i;
		} if(x > 1) pr[++cpr] = x; // 找到所有 n 的质因子
	dfs(1, 1), sort(dv + 1, dv + cdv + 1), reverse(dv + 1, dv + cdv + 1); // 别忘了排序
}
gp_hash_table <ll, bool> mp; // 哈希表标记
int main() {
	cin >> n >> k, init();
	for(ll i = 1; i < k; i++) mp[__gcd(read(), n)] = 1;
	v = __gcd(read(), n);
	for(int i = 1; i <= cdv; i++) {
		if(mp.find(dv[i]) != mp.end()) {
			for(int j = 1; j <= cpr; j++)
				if(dv[i] % pr[j] == 0) mp[dv[i] / pr[j]] = 1;
		} else if(v % dv[i] == 0) ans = n / dv[i];
	} cout << ans << endl;
	return 0;
}