「POI2011 R2」保险箱 Strongbox 题解

题目解析

我们有一个模 $n$ 的加法群，已知：

• 位置 $m_k$ 能打开保险柜
• 位置 $m_1, m_2, \ldots, m_{k-1}$ 不能打开保险柜
• 如果 $x$ 和 $y$ 能打开，那么 $(x+y) \bmod n$ 也能打开

我们需要找出最多可能有多少个位置能打开保险柜。

关键观察

1. 群结构：能打开的位置构成一个加法子群
2. 生成元：由于 $m_k$ 能打开，子群至少包含 $m_k$ 生成的循环子群
3. 排除元素：$m_1, m_2, \ldots, m_{k-1}$ 不在子群中
4. 最大子群：我们要找包含 $m_k$ 但不包含 $m_1, \ldots, m_{k-1}$ 的最大子群

算法思路

数学转化

设 $d = \gcd(n, m_k)$，则 $m_k$ 生成的子群大小为 $n/d$。

但我们需要的是最大的可能子群，因此考虑 $n$ 的约数：

设最终子群的大小为 $n/g$，其中 $g$ 是 $n$ 的约数。那么子群就是 $g$ 的倍数模 $n$ 的集合。

条件：

1. $m_k$ 在子群中 ⇒ $g \mid m_k$
2. $m_1, \ldots, m_{k-1}$ 不在子群中 ⇒ $g \nmid m_i$ 对于 $i=1,\ldots,k-1$

求解步骤

1. 计算候选约数：找出所有 $n$ 和 $m_k$ 的公约数
2. 筛选约数：排除那些能整除某个 $m_i$ ($1 \le i \le k-1$) 的约数
3. 找最大子群：在剩余约数中，选择最小的 $g$（因为子群大小为 $n/g$，$g$ 越小，子群越大）

优化方法

由于 $n$ 可达 $10^{14}$，不能直接分解所有约数。优化策略：

• 先计算 $G = \gcd(n, m_k)$
• 找出 $G$ 的所有质因子
• 初始设 $g = G$
• 对于每个质因子 $p$，尝试将 $g$ 除以 $p$（如果还能满足 $g \mid m_k$ 且 $g \nmid m_i$ 对所有 $i<k$）
• 最终 $g$ 就是满足条件的最小约数
• 答案 = $n / g$

复杂度分析

• 时间复杂度：$O(k \log n)$
• 空间复杂度：$O(k + \log n)$

这种方法利用了数论性质，避免了直接处理大数的所有约数，能够在给定约束下高效运行。

示例解释

对于样例：

• $n = 42$, $m_k = 24$
• $G = \gcd(42, 24) = 6$
• 检查 $m_1=28, m_2=31, m_3=10, m_4=38$
• 最终找到 $g = 3$（满足 $3 \mid 24$ 且 $3 \nmid 28,31,10,38$）
• 答案 = $42 / 3 = 14$