[POI 2011] SEJ-Strongbox

这是一道非常经典的数论题目，考察了对模运算、最大公约数（GCD）以及群论基础（循环群子群）的理解。

下面我将从数学原理、解题思路到具体的算法优化为你详细分析这道题。

1. 数学模型与题意转化

题目要求找一个密码集合 $S \subseteq \{0, 1, \dots, n-1\}$，满足若 $a, b \in S \implies (a+b) \bmod n \in S$。 在抽象代数中，这意味着 $S$ 是整数模 $n$ 加法群 $\mathbb{Z}_n$ 的一个子群。

核心性质：

1. 子群结构：$\mathbb{Z}_n$ 的任何子群都是循环群，且由 $n$ 的某个因子 $d$ 生成。 即 $S = \{0, d, 2d, 3d, \dots \}$，其中 $d \mid n$。 集合的大小（密码个数）为 $|S| = n/d$。
2. 目标：我们要让密码个数 $|S|$ 最大，等价于要让生成元 $d$ 最小。

2. 限制条件分析

题目给出了一些尝试记录：

• 失败的尝试 ($m_1, \dots, m_{k-1}$)：这些数不在集合 $S$ 中。 这意味着它们不能被 $d$ 整除。即：$m_i \not\equiv 0 \pmod d$。
• 成功的尝试 ($m_k$)：这个数在集合 $S$ 中。 这意味着它是 $d$ 的倍数。即：$m_k \equiv 0 \pmod d$。

综合条件： 我们需要找到一个整数 $d$，满足以下三个条件，并使 $d$ 最小：

1. $d$ 是 $n$ 的因子 ($d \mid n$)。
2. $d$ 是 $m_k$ 的因子 ($d \mid m_k$)。
   • 由 1 和 2 可知，$d$ 必须是 $\gcd(m_k, n)$ 的因子。记 $G = \gcd(m_k, n)$。
3. 对于所有 $1 \le i < k$，$d$ 不是 $m_i$ 的因子。
   • 注意：因为 $d \mid n$，判断 “$d$ 不是 $m_i$ 的因子” 等价于判断 “$d$ 不是 $\gcd(m_i, n)$ 的因子”。如果是 $m_i$ 的因子，也就是 $\gcd(m_i, n)$ 的因子。进一步地，因为我们只在 $G$ 的因子中找 $d$，所以这等价于判断 $d$ 不是 $\gcd(m_i, G)$ 的因子。

3. 朴素算法 vs 优化算法

朴素思路： 找出 $G = \gcd(m_k, n)$ 的所有因子，从小到大枚举每一个因子 $d$，检查它是否整除任意一个 $m_i$。

• 问题：虽然 $n$ 的因子个数通常不多，但 $m_i$ 的数量 $k$ 高达 $2.5 \times 10^5$。每次枚举 $d$ 都要遍历一遍 $m_i$，时间复杂度约为 $O(\text{因子数} \times k)$，可能会超时。

优化思路（利用因子的整除性质）： 我们可以反向思考：哪些因子是不行的？

1. 计算 $G = \gcd(m_k, n)$，找出 $G$ 的所有因子，存入数组 divs。
2. 对于每个失败的尝试 $m_i$，计算 $tmp = \gcd(m_i, G)$。
   • $tmp$ 显然也是 $G$ 的因子。
   • 如果 $d$ 能整除 $m_i$，那么 $d$ 一定能整除 $tmp$。
   • 因此，$tmp$ 以及 $tmp$ 的所有因子都不能作为我们要找的 $d$。
3. 我们可以标记所有“被禁用”的因子。
   • 首先标记所有出现的 $\gcd(m_i, G)$。
   • 然后进行传递：如果一个数被禁用了，它的所有因子也应该被禁用。为了高效，我们把 divs 从大到小遍历，如果 divs[j] 被标记了，且 divs[i] 是 divs[j] 的因子，那么 divs[i] 也标记为不可用。
4. 最后，在未被标记的因子中，取最小的那个作为 $d$。

4. 算法流程详解

1. 初始化：读取 $n, k$ 和数组 $m$。
2. 计算基准 G：$G = \gcd(m_k, n)$。
3. 获取因子：求出 $G$ 的所有因子，存入数组 divs 并排序。
   • 由于 $n \le 10^{14}$，$\sqrt{G} \le 10^7$，可以直接枚举求解。因子个数（记为 $D$）对于 $10^{14}$ 范围内的数通常很少（几千到一两万）。
4. 标记初始冲突：
   • 建立一个布尔数组 bad[] 对应 divs。
   • 遍历 $m_1$ 到 $m_{k-1}$：
     • 计算 $val = \gcd(m_i, G)$。
     • 在 divs 中二分查找 $val$ 的位置，将该位置标记为 bad = true。
5. 向下传播标记（优化核心）：
   • 如果我们暴力两层循环判断 $divs[j] \% divs[i] == 0$，复杂度是 $O(D^2)$，当 $D \approx 20000$ 时约为 $4 \times 10^8$，有点危险但可能卡过。
   • 更优做法：预处理 $G$ 的所有质因子 $P$。
   • 从大到小遍历 divs 的每个元素 divs[i]。
   • 如果 divs[i] 是 bad 的：
     • 遍历所有质因子 $p \in P$。
     • 如果 divs[i] 能被 $p$ 整除，说明 divs[i] / p 也是 $G$ 的因子。
     • 在 divs 中找到 divs[i] / p 的位置，将其标记为 bad。
   • 这种做法复杂度大幅降低，接近 $O(D \times \log G)$。
6. 寻找答案：
   • 从小到大遍历 divs，找到第一个 bad 为 false 的因子 $d$。
   • 输出答案 $n / d$。

5. 代码实现参考 (C++)

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

        #include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

typedef long long ll;

// 计算最大公约数
ll gcd(ll a, ll b) {
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

int main() {
    // 优化 I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll n;
    int k;
    if (!(cin >> n >> k)) return 0;

    vector<ll> m(k);
    for (int i = 0; i < k; ++i) {
        cin >> m[i];
    }

    // 1. 计算 G = gcd(m_k, n)
    // 题目中 m 是 0-indexed 输入，所以第 k 次是 m[k-1]
    ll mk = m[k - 1];
    ll G = gcd(mk, n);

    // 2. 找出 G 的所有因子
    vector<ll> divs;
    for (ll i = 1; i * i <= G; ++i) {
        if (G % i == 0) {
            divs.push_back(i);
            if (i * i != G) {
                divs.push_back(G / i);
            }
        }
    }
    sort(divs.begin(), divs.end());

    // 3. 标记初始冲突
    // bad[i] 表示 divs[i] 是否不能作为 d
    vector<bool> bad(divs.size(), false);

    for (int i = 0; i < k - 1; ++i) {
        ll val = gcd(m[i], G);
        // 二分查找 val 在 divs 中的位置
        auto it = lower_bound(divs.begin(), divs.end(), val);
        if (it != divs.end() && *it == val) {
            int idx = distance(divs.begin(), it);
            bad[idx] = true;
        }
    }

    // 4. 传播标记
    // 找出 G 的所有质因子，用于加速传播
    vector<ll> prime_factors;
    ll tempG = G;
    for (ll i = 2; i * i <= tempG; ++i) {
        if (tempG % i == 0) {
            prime_factors.push_back(i);
            while (tempG % i == 0) tempG /= i;
        }
    }
    if (tempG > 1) prime_factors.push_back(tempG);

    // 从大到小遍历
    for (int i = divs.size() - 1; i >= 0; --i) {
        if (bad[i]) {
            ll current = divs[i];
            for (ll p : prime_factors) {
                if (current % p == 0) {
                    ll target = current / p;
                    // 二分查找 target 的位置
                    auto it = lower_bound(divs.begin(), divs.end(), target);
                    if (it != divs.end() && *it == target) {
                        bad[distance(divs.begin(), it)] = true;
                    }
                }
            }
        }
    }

    // 5. 寻找最小的合法 d
    for (int i = 0; i < divs.size(); ++i) {
        if (!bad[i]) {
            cout << n / divs[i] << endl;
            return 0;
        }
    }

    return 0;
}

    

总结

• 复杂度：
  • 求因子：$O(\sqrt{n})$ (实际上是 $\sqrt{G}$)。
  • 初始标记：$O(k \log (\text{因子数})) \approx O(k \log n)$。
  • 传播标记：$O(\text{因子数} \times \text{质因子数} \times \log (\text{因子数}))$。
  • 整体能够轻松通过 $10^{14}$ 和 $2.5 \times 10^5$ 的数据规模。
• 关键点：
  • 意识到题目求的是 $\mathbb{Z}_n$ 的子群。
  • 利用 $G = \gcd(m_k, n)$ 缩小搜索范围。
  • 利用 $d \mid val \implies d$ 也不合法的性质，从大到小筛选因子。