自动搬运

查看原文

来自洛谷，原作者为

	_hud Hi

搬运于2025-08-24 23:17:21，当前版本为作者最后更新于2025-06-06 20:44:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题解：P12677 Brooklyn Round 1 & NNOI Round 1 A - Flying Flower

题目大意

给定两个序列 $a$（长度为 $n$）和 $b$（长度为 $m$），进行 $q$ 次游戏，每次游戏给定一个整数 $k$。规则如下：双方轮流报数，报的数必须来自自己对应的序列，且该数的质因子要包含 $k$，并且严格大于对方上一个人报的数。小 X 先手，小 Z 后手。若某人无数可报则该人输。若 $k$ 不是质数，直接判定小 Z 获胜。

对于每个查询 $k$，在两人都采用最优策略的前提下，判断哪方必胜。

思路分析

首先，对于给定的整数 $k$，分别定义：

$$A_k \;=\;\{\,a_i\mid k\mid a_i\,\},\quad B_k \;=\;\{\,b_i\mid k\mid b_i\,\}, $$

即 $A_k$ 和 $B_k$ 分别是序列 $a$ 与 $b$ 中所有能被 $k$ 整除的元素集合。

分析题意，分类讨论：

1. $k$ 不是质数。直接输出 Z 即可。
2. $A_k$ 为空，即序列 $a$ 中没有一个数满足其质因子含有 $k$。直接输出 Z 即可。
3. $A_k$ 不为空时，若：
   • $\max(A_k)\ge \max(B_k)$，小 X 可以第一步直接报出 $\max(A_k)$。由于 $\max(A_k)\ge \max(B_k)$，小 Z 在 $B_k$ 中找不到大于 $\max(A_k)$ 的数，故只能认输，小 X 获胜。
   • 反之同理，若 $\max(A_k)<\max(B_k)$，则无论小 X 第 一步报出哪一个 $x\in A_k$，由于 $x\le \max(A_k)<\max(B_k)$，小 Z 都可以直接报出 $\max(B_k)$，此时小 X 无法报出大于 $\max(B_k)$ 的数，小 Z 获胜。

分析完思路，再来讲讲如何实现。我们可以用线性筛预处理出所有质数，然后再对每一个序列 $a$ 和序列 $b$ 中的数进行质因数分解，计算出 $A_k$ 和 $B_k$ 即可。具体可以看代码。

代码

#include <bits/stdc++.h>
using namespace std;
struct IO { // 不重要的快读快写
    #define SIZE (1 << 20)
    #define isd(x) ((x) > 47 && (x) < 58)
    char buf[SIZE], pbuf[SIZE], *p1, *p2, *pp;
    IO() : p1(buf), p2(buf), pp(pbuf) {}
    ~IO() { fwrite(pbuf, 1, pp - pbuf, stdout); }
    inline int gc() {
        if(p1 == p2) p2 = (p1 = buf) + fread(buf, 1, SIZE, stdin);
        return p1 == p2 ? ' ' : *p1++;
    }
    inline int read(int &x) {
        x = 0; char c;
        for(c = gc(); !isd(c); c = gc());
        for(; isd(c); c = gc()) x = (x << 1) + (x << 3) + (c & 15);
        return x;
    }
    inline void push(const char &c) {
        if(pp - pbuf == SIZE) {
            fwrite(pbuf, 1, SIZE, stdout);
            pp = pbuf;
        }
        *pp++ = c;
    }
} io;
const int M = 8e6 + 10;
bitset<M> isp;        // isp[i] 标记 i 是否为质数
int pn[M >> 1], cnt;  // pn[] 存储所有质数，cnt 为质数个数
int maxa[M], maxb[M]; // maxa[p] 表示序列 a 中能被质因子 p 整除的数的最大值，maxb 同理
signed main() {
    // 线性筛求质数
    isp.set();
    isp[0] = isp[1] = 0;  // 0、1 不是质数
    for(int i = 2; i < M; ++i) {
        if(isp[i]) pn[++cnt] = i;
        for(int j = 1; j <= cnt && 1ll * i * pn[j] < M; ++j) {
            isp[i * pn[j]] = 0;
            if (i % pn[j] == 0) break;
        }
    }
    int n, m, q; io.read(n), io.read(m), io.read(q);
    // 处理序列 a，更新 maxa[p]
    for(int i = 1; i <= n; ++i) {
        int raw, tmp; raw = io.read(tmp);
        // 质因数分解
        for(int j = 1; 1ll * pn[j] * pn[j] <= raw; ++j)
            if(tmp % pn[j] == 0) {
                tmp /= pn[j]; 
                // 如果 pn[j] 是 raw 的一个质因子，则更新 maxa[pn[j]]
                maxa[pn[j]] = max(maxa[pn[j]], raw);
                while(tmp % pn[j] == 0) tmp /= pn[j]; // 去除该质因子所有次幂
            }
        if(tmp > 1) maxa[tmp] = max(maxa[tmp], raw);
        
    }
    // 处理序列 b，更新 maxb[p]
    for(int i = 1; i <= m; ++i) {
        int raw, tmp; raw = io.read(tmp); 
        for(int j = 1; 1ll * pn[j] * pn[j] <= raw; ++j)
            if(tmp % pn[j] == 0) {
                tmp /= pn[j], maxb[pn[j]] = max(maxb[pn[j]], raw);
                while (tmp % pn[j] == 0) tmp /= pn[j];
            }
        if(tmp > 1) maxb[tmp] = max(maxb[tmp], raw);
    }
    while(q--) {
        int k; io.read(k);
        if(!isp[k] || !maxa[k]) { io.push('Z'), io.push('\n'); continue; }
        io.push(maxa[k] >= maxb[k] ? 'X' : 'Z'), io.push('\n');
    }
    return 0; // 完结撒花
}