Educational Codeforces Round 187 (Rated for Div. 2)-CF-Edu-187-D. Divisibility Game（较大数据量下 vector 套 vector 的调和级数因数分解会出问题）（觉得有点把握不住，就上 int128，一般就比较难卡掉了）（在高版本 C++，要自己定义 lcm 函数就写 lcm128 什么的，就写 lcm 可能给你直接调 std::lcm）

题目大意

题目大意

Alice 和 Bob 在玩一个游戏。给定两个数组：包含 $n$ 个元素的数组 $a$ 和包含 $m$ 个元素的数组 $b$。

两人轮流进行操作，Alice 先手。在每个回合中，玩家需要从数组 $a$ 中选择一个数字 $x$，并从数组 $b$ 中选择一个数字 $y$。

• Alice 的规则：选择的 $y$ 必须能被 $x$ 整除。

• Bob 的规则：选择的 $y$ 必须不能被 $x$ 整除。

选定 $x$ 和 $y$ 后，$y$ 会从数组 $b$ 中被移除（如果数组中存在多个相同的 $y$，只移除其中一个），而 $x$ 仍然保留在数组 $a$ 中。无法进行合法操作（即无法选出满足自身规则的 $x$ 和 $y$）的玩家将输掉游戏。

假设双方都采取最优策略，请判断谁会赢得游戏。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

对于每个测试用例：
第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 10^6$）。
第二行包含 $n$ 个整数 $a_i$（$1 \le a_i \le n+m$），表示数组 $a$ 的元素。
第三行包含 $m$ 个整数 $b_i$（$1 \le b_i \le n+m$），表示数组 $b$ 的元素。

保证所有测试用例中 $n$ 的总和以及 $m$ 的总和均不超过 $10^6$。

输出格式

对于每个测试用例，输出获胜者的名字：如果 Alice 赢，输出 Alice；如果 Bob 赢，输出 Bob。

样例输入

3
9 3
3 2 4 2 2 4 4 2 4
6 7 12
10 3
3 2 5 4 2 5 3 4 4 4
10 7 13
1 5
1
1 2 3 4 5

样例输出

Alice
Bob
Alice

样例解释

对于第一个测试用例，Alice 的获胜过程如下：

1. Alice 的回合：选择 $x=3, y=6$（$6$ 能被 $3$ 整除）。操作后 $6$ 从数组 $b$ 中移除，此时 $b=[7, 12]$。

2. Bob 的回合：选择 $x=3, y=7$（$7$ 不能被 $3$ 整除）。Bob 在这个回合只能选择 $y=7$，因为对于 $y=12$，数组 $a$ 中找不到任何不能整除它的 $x$。操作后 $7$ 从数组 $b$ 中移除，此时 $b=[12]$。

3. Alice 的回合：选择 $x=4, y=12$（$12$ 能被 $4$ 整除）。操作后 $12$ 从数组 $b$ 中移除，此时数组 $b$ 变为空。

4. Bob 的回合：数组 $b$ 已经为空，Bob 无法进行任何操作，因此 Bob 输掉游戏，Alice 获胜。

思路讲解

OK，我们说回来。这个D为什么交了5发还是没过呢？主要是因为就是这个D，它的数据量比较大。使用Victor victor或者victor的这种调和级数写法呢，它这个时间会超。可以使用vis 数组标记所有 a 的倍数。这样子可以避免卡常。

ll cnt_un_divide=0,cnt_all_divide=0;
vector<char> vis(N+M+2);
for (auto a:A) {
    for (ll i=1;i<=N+M;++i) {
        if (i*a>N+M) {
            break;
        }
        vis[i*a]=true;
    }
}

然后为什么标题里面提了不要用 while 循环？是因为涉及累加的逻辑（在 D 的对拍暴力程序当中），直接 continue 以后，while 循环的这个累加就崩掉了。

AC代码

AC
https://codeforces.com/contest/2203/submission/364454955

源代码

/**
 * Problem: D. Divisibility Game
 * Contest: Educational Codeforces Round 187 (Rated for Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2203/problem/D
 * Created: 2026-02-25 22:56:31
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)2e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */

i128 lcm128(i128 a,i128 b) {
    i128 res=a*b/__gcd(a,b);
    return res;
}
// vector<ll> factor[MAXN];
void Solve() {
    ll N,M;
    cin >> N >> M;
    vector<ll> A(N),B(M);
    for (int i=0;i<N;++i) {
        cin>>A[i];
    }
    for (int i=0;i<M;++i) {
        cin>>B[i];
    }
    // vector<vector<ll>> factor(N+M+2);
    // factor.reserve(N+M+2);
    // for (int i=1;i<=N+M;++i) {
    //     for (int j=1;j<=N+M;++j) {
    //         if (i*j>N+M) {
    //             break;
    //         }
    //         factor[i*j].push_back(i);
    //     }
    // }
    sort(all(A));
    A.resize(unique(all(A))-A.begin());
    __int128 acc_lcm=A[0];
    for (int i=1;i<A.size();++i) {
        acc_lcm=lcm128(acc_lcm,A[i]);
    }
    ll cnt_un_divide=0,cnt_all_divide=0;
    vector<char> vis(N+M+2);
    for (auto a:A) {
        for (ll i=1;i<=N+M;++i) {
            if (i*a>N+M) {
                break;
            }
            vis[i*a]=true;
        }
    }
    for (int i=0;i<M;++i) {
        if (!vis[B[i]]) {
            cnt_un_divide++;
        }
    }

    for (int i=0;i<M;++i) {
        if (B[i]%acc_lcm==0) {
            cnt_all_divide++;
        }
    }

    ll rem=M-cnt_all_divide-cnt_un_divide;
    for (int idx=1;;++idx) {
        if (idx&1) {
            if (rem>0) {
                rem--;
                continue;
            }
            if (cnt_all_divide>0) {
                cnt_all_divide--;
                continue;
            }
            cout<<"Bob\n";
            return;
        }else {
            if (rem>0) {
                rem--;
                continue;
            }
            if (cnt_un_divide>0) {
                cnt_un_divide--;
                continue;
            }
            cout<<"Alice\n";
            return;
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif
    cin >> lT;
    for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/contest/2203/submission/364454955

1
9 3
3 2 4 2 2 4 4 2 4
6 7 12

1
1 5
1
1 2 3 4 5

*/

心路历程（WA，TLE，MLE……）

后面还被系统测试阴了一手，把这个LCM改成128，用INT128就可以了，这个叫什么，当时其实我就知道这里应该是会有点问题的，想用这个128嘛，但是可能还是犹豫还是犹豫了。

i128 lcm128(i128 a,i128 b) {
    i128 res=a*b/__gcd(a,b);
    return res;
}