题解：P12677 Flying Flower

ZesteYdaZ · 2025-06-01 13:24:53 · 题解

题目链接

https://www.luogu.com.cn/problem/P12677

思路分析

易于想到，为使对方尽可能难以报出下一个数，自己应该报出可行的最大数。

我们可以分别记录二人的数列中含有某个质因子的最大数。比较它们的大小，拥有较大数者获胜。

注意一下 k 为合数和二人均无合法数的特殊情况。

Code

#include <bits/stdc++.h>

using namespace std;

template <typename T>
void read_arr(int n, T *arr) {
    for (int i = 1; i <= n; ++ i) cin >> arr[i];
    return;
}

constexpr int N = 5e5 + 5, M = 8e6 + 5;

int n, m, q, a[N], b[N], lst_a[M], lst_b[M];

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

    cin >> n >> m >> q; read_arr(n, a), read_arr(m, b);

    sort(a + 1, a + n + 1), sort(b + 1, b + m + 1);

    // 分解质因数，记录含有某个质因子的最大数 
    for (int i = 1; i <= n; ++ i) {
        int num = a[i];
        for (int j = 2; j * j <= num; ++ j)
            if (num % j == 0) {
                lst_a[j] = a[i];

                while (num % j == 0) num /= j;
            }
        if (num != 1) lst_a[num] = a[i];
    }

    for (int i = 1; i <= m; ++ i) {
        int num = b[i];
        for (int j = 2; j * j <= num; ++ j)
            if (num % j == 0) {
                lst_b[j] = b[i];

                while (num % j == 0) num /= j;
            }
        if (num != 1) lst_b[num] = b[i];
    }

    // lambda 表达式，相当于轻型函数 
    auto check_prime = [](int x) -> bool {
        if (x <= 1) return true;
        for (int i = 2; i * i <= x; ++ i)
            if (x % i == 0) return false;
        return true;
    };

    for (int _ = 0; _ < q; ++ _) {
        int x1; cin >> x1;

        if (check_prime(x1) == false) cout << "Z\n"; // k 为合数，依题目要求输出 'Z' 
        else if (lst_a[x1] == 0 && lst_b[x1] == 0) cout <<"Z\n"; // 两人均无数可报 
        else cout << "XZ"[lst_a[x1] < lst_b[x1]] << '\n'; // 拥有较大数者获胜 
    }
    return 0;
}