题解： Multiple Lamps

问题简述

有 $n$ 盏灯，初始全灭。按钮 $i$ 会切换所有编号为 $i$ 的倍数的灯。
需要按至少一个按钮（每个最多一次），且满足 $m$ 条约束：若按了 $u_i$，则必须按 $v_i$。
要求最终亮灯数 $\le \left\lfloor \frac{n}{5} \right\rfloor$，输出任意一组按下的按钮，或 $-1$ 表示无解。

关键观察

1. 按下所有按钮后的结果
   灯 $i$ 被所有 $i$ 的约数按钮切换。
   它最终亮着的充要条件是 $i$ 的约数个数为奇数，即 $i$ 是完全平方数。
   所以亮灯数为 $\lfloor \sqrt{n} \rfloor$。

2. 何时直接按所有按钮可行
   需要 $\lfloor \sqrt{n} \rfloor \le \left\lfloor \frac{n}{5} \right\rfloor$。
   经检验，当 $n \ge 20$ 时该不等式成立。
   因此对于 $n \ge 20$，直接输出所有按钮 $1,2,\dots,n$ 即可。

3. 小数据范围的处理
   当 $n \le 19$ 时，$\left\lfloor \frac{n}{5} \right\rfloor \le 3$，即最终亮灯数最多为 $3$。
   我们可以枚举所有可能的最终亮灯集合（大小为 $0,1,2,3$），并反向构造按下的按钮集合。

构造方法

假设我们已经知道最终哪些灯是亮的（目标状态 $T$ 是一个 $n$ 位二进制掩码）。
如何找到一组按钮，使得最终状态恰好为 $T$？

贪心构造：
从 $i=1$ 到 $n$ 依次考虑按钮 $i$。
设当前灯的状态为 $cur$（初始为 $0$）。如果灯 $i$ 的状态 $cur_i$ 与目标 $T_i$ 不同，则按下按钮 $i$，并更新所有 $i$ 的倍数的灯。
因为按钮 $i$ 只影响编号 $\ge i$ 的灯，且我们按顺序处理，所以这种贪心一定可以得到唯一解（每个灯的状态最终由其约数中最大的被按按钮决定）。
因此我们可以由 $T$ 唯一确定要按的按钮集合 $B$（用掩码表示）。

检查约束

得到 $B$ 后，需要验证：

• $B \neq 0$（至少按一个按钮）
• 对每条约束 $(u,v)$：若 $u \in B$，则必须有 $v \in B$。
  这可以通过预处理每个按钮 $u$ 的“必须按”集合 $must[u]$（掩码），然后检查 $(B \& must[u]) == must[u]$ 即可。

算法流程

1. 若 $n \ge 20$：输出 $1,2,\dots,n$，结束。
2. 预处理：
   • lamp_mask[i]：按钮 $i$ 影响的灯的掩码（$i$ 从 $0$ 到 $n-1$ 编号）。
   • must[i]：若按按钮 $i$，则必须按的所有按钮的掩码。
3. 枚举所有大小 $\le 3$ 的目标亮灯子集 $T$：
   • 使用贪心构造按钮集 $B$。
   • 检查 $B$ 是否非空且满足所有约束。
   • 若满足，输出 $B$ 中按钮编号（$+1$ 转回 $1$-based）。
4. 若枚举完仍未找到，输出 $-1$。

复杂度分析

• $n \ge 20$：每个测试 $O(n)$。
• $n \le 19$：枚举子集数最多$$\sum_{k=0}^{3} \binom{19}{k} = 1 + 19 + 171 + 969 = 1160. $$每次构造和检查均为 $O(n + m)$（可用位运算优化到 $O(n)$ 左右）。
  由于所有测试的 $n,m$ 总和 $\le 2\times 10^5$，总时间非常充裕。

代码实现（C++）

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<pair<int,int>> constraints(m);
    for (int i = 0; i < m; ++i) {
        cin >> constraints[i].first >> constraints[i].second;
        --constraints[i].first;
        --constraints[i].second;
    }

    // 情况1：n >= 20
    if (n >= 20) {
        cout << n << "\n";
        for (int i = 1; i <= n; ++i) {
            cout << i << " \n"[i == n];
        }
        return;
    }

    // 情况2：n <= 19
    vector<int> lamp_mask(n, 0);
    for (int i = 0; i < n; ++i) {
        int step = i + 1;
        for (int j = i; j < n; j += step) {
            lamp_mask[i] |= 1 << j;
        }
    }

    vector<int> must(n, 0);
    for (auto [u, v] : constraints) {
        must[u] |= 1 << v;
    }

    vector<int> ans_buttons;
    bool found = false;

    auto check = [&](int T) {
        int cur = 0, B = 0;
        for (int i = 0; i < n; ++i) {
            if (((cur >> i) & 1) != ((T >> i) & 1)) {
                B |= 1 << i;
                cur ^= lamp_mask[i];
            }
        }
        if (B == 0) return false;
        for (int i = 0; i < n; ++i) {
            if ((B >> i) & 1) {
                if ((B & must[i]) != must[i]) return false;
            }
        }
        for (int i = 0; i < n; ++i) {
            if ((B >> i) & 1) ans_buttons.push_back(i + 1);
        }
        return true;
    };

    // 枚举大小为 0..3 的子集
    if (check(0)) found = true;
    for (int i = 0; i < n && !found; ++i) {
        if (check(1 << i)) found = true;
    }
    for (int i = 0; i < n && !found; ++i) {
        for (int j = i + 1; j < n && !found; ++j) {
            if (check((1 << i) | (1 << j))) found = true;
        }
    }
    for (int i = 0; i < n && !found; ++i) {
        for (int j = i + 1; j < n && !found; ++j) {
            for (int k = j + 1; k < n && !found; ++k) {
                if (check((1 << i) | (1 << j) | (1 << k))) found = true;
            }
        }
    }

    if (!found) {
        cout << "-1\n";
    } else {
        cout << ans_buttons.size() << "\n";
        for (size_t i = 0; i < ans_buttons.size(); ++i) {
            cout << ans_buttons[i] << " \n"[i + 1 == ans_buttons.size()];
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

总结

• 利用完全平方数的性质，$n \ge 20$ 时直接全按。
• 小范围暴力枚举所有可能的最终亮灯状态（最多 $3$ 盏），贪心反推按钮集并验证约束。
• 时间复杂度 $O(\sum n + \sum m \cdot 1160)$，实际运行极快。