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

· · 题解

题解：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 整除的元素集合。

分析题意，分类讨论：

  3. - $\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; // 完结撒花
}