A1508.[COCI-2013_2014-contest1]#3 ORGANIZATOR

---

题目分析（组织者）

Mirko 要组织一场比赛，有 N 个俱乐部参加。每个俱乐部有若干成员。
Mirko 需要选择一个队伍大小 k，使得：

• 每个俱乐部只能派出人数为 k 的倍数的队伍（即每个队伍恰好 k 人，且队员来自同一俱乐部）
• 每个俱乐部可以派出任意多支队伍参加资格赛
• 每个俱乐部中成绩最好的那支队伍进入决赛
• 至少有两个俱乐部能进入决赛（否则太无聊）

目标：选择 k，使决赛总人数（k × 进入决赛的俱乐部数）最大。

核心思路

• 如果 k 固定，一个俱乐部能进决赛当且仅当其成员数 ≥ k，并且成员数是 k 的倍数（因为必须恰好凑成整队）。
• 实际上，因为每个俱乐部只派一支队伍进决赛，且人数必须整除 k，所以只有那些人数是 k 的倍数的俱乐部才有资格。
• 因此，对于每个可能的 k，符合条件的俱乐部数 = 人数为 k 的倍数的俱乐部个数。
• 我们只需枚举所有可能的 k，用倍数累加的方式快速统计出每个 k 对应的俱乐部数，然后取 k × 俱乐部数的最大值（且俱乐部数 ≥ 2）。

枚举范围

• 人数最大为 2×10^6，所以 k 只需枚举到 max(a[i])。
• 因为 k 大于最大值时，不可能有任何一个俱乐部人数是 k 的倍数（除了 0，但人数 ≥1），故俱乐部数最多为 0 或 1，无法满足至少两个的要求。

---

代码实现（all AC，可放心食用）

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, mx = 0;
    cin >> n;
    vector<int> cnt(2000001, 0); // 计数数组，下标表示人数

    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        cnt[x]++;
        if (x > mx) mx = x; // 记录最大人数
    }

    long long ans = 0;
    // 枚举所有可能的队伍大小 k
    for (int k = 1; k <= mx; ++k) {
        long long total = 0; // 人数是 k 的倍数的俱乐部个数
        for (int m = k; m <= mx; m += k) {
            total += cnt[m];
        }
        if (total >= 2) {
            ans = max(ans, k * total);
        }
    }

    cout << ans << '\n';
    return 0; // 不忘好习惯
}

代码详解

1. 输入与计数

vector<int> cnt(2000001, 0);
for (int i = 0; i < n; ++i) {
    int x;
    cin >> x;
    cnt[x]++;
    if (x > mx) mx = x;
}

• 使用 cnt 数组记录每个俱乐部人数出现的次数。
• 同时记录最大人数 mx，减少枚举范围。

2. 枚举 k 并统计倍数

for (int k = 1; k <= mx; ++k) {
    long long total = 0;
    for (int m = k; m <= mx; m += k) {
        total += cnt[m];
    }
    if (total >= 2) {
        ans = max(ans, k * total);
    }
}

• 外层循环枚举队伍大小 k。
• 内层循环遍历所有 k 的倍数 m，累加 cnt[m]，得到人数是 k 的倍数的俱乐部总数。
• 如果总数 ≥ 2，则满足至少两个俱乐部的要求，更新答案。

3. 输出

cout << ans << '\n';

• 输出最大可能的决赛人数。

示例分析

示例 1

输入：

3
1 2 4

计数：cnt[1]=1, cnt[2]=1, cnt[4]=1, mx=4

• k=1：倍数 1,2,3,4 → total=1+1+0+1=3 ≥2 → ans=1×3=3
• k=2：倍数 2,4 → total=1+1=2 ≥2 → ans=max(3, 2×2=4)=4
• k=3：倍数 3 → total=0 → 跳过
• k=4：倍数 4 → total=1 → 跳过

结果：4

示例 2

输入：

2
1 5

计数：cnt[1]=1, cnt[5]=1, mx=5

• k=1：倍数 1,2,3,4,5 → total=1+0+0+0+1=2 ≥2 → ans=1×2=2
• k=2：倍数 2,4 → total=0 → 跳过
• k=3：倍数 3 → total=0
• k=4：倍数 4 → total=0
• k=5：倍数 5 → total=1 → 跳过

结果：2

示例 3

输入：

5
4 6 3 8 9

计数：cnt[3]=1, cnt[4]=1, cnt[6]=1, cnt[8]=1, cnt[9]=1, mx=9

• k=1：倍数 1…9 → total=5 ≥2 → ans=5
• k=2：倍数 2,4,6,8 → total=0+1+1+1=3 ≥2 → ans=2×3=6
• k=3：倍数 3,6,9 → total=1+1+1=3 ≥2 → ans=3×3=9
• k=4：倍数 4,8 → total=1+1=2 ≥2 → ans=max(9, 4×2=8)=9
• k=5：倍数 5,10 → total=0
• k=6：倍数 6 → total=1
• k=7：倍数 7 → 0
• k=8：倍数 8 → 1
• k=9：倍数 9 → 1

结果：9

复杂度分析

• 时间复杂度：(O(M \log M))，其中 (M = \max(a_i) \le 2\times 10^6)。
  内层循环的总次数是 (M \cdot H_M \approx M \ln M)，实测约 (4.2\times 10^7) 次操作，可以在 1 秒内完成。
• 空间复杂度：(O(M))，用于计数数组。

---

常见错误点

• 忘记至少两个俱乐部：需要判断 total >= 2 才更新答案。
• 枚举范围过大：只需枚举到最大人数，而不是到 2×10^6（虽然枚举到 2×10^6 也不会超时，但没必要）。
• 直接使用俱乐部数量 N 代替 M：如果某个俱乐部人数很大，但 k 很小时，需要统计到 M。
• 溢出问题：答案可能超过 int 范围，使用 long long 存储。

总结

本题的核心是利用倍数累加来快速统计每个 k 对应的俱乐部数量。
这种思想在数论、计数问题中很常见（如统计因数、倍数）。
通过枚举所有可能的 k 并累加其倍数，我们在 (O(M \log M)) 的时间内解决了问题。
注意边界条件和数据类型，即可轻松通过。