题目解析

题意概括

有 $n$ 张卡牌，每张卡牌有两个战斗力值 $a_i$ 和 $b_i$。对于每张卡牌，可以选择 $a_i$ 或 $b_i$ 作为它的最终战斗力。目标是选择一种方案，使得所有卡牌最终战斗力的 最大公约数 (GCD) 尽可能大，并输出这个最大的 GCD。

算法思路

核心思想

如果我们固定一个候选答案 $g$，那么要求每张卡牌至少有一个战斗力值能被 $g$ 整除。
也就是说，对于第 $i$ 张卡牌，必须满足： [ g \mid a_i \quad \text{或} \quad g \mid b_i ]

反过来，如果我们想判断 $g$ 是否可能成为最终答案，只需要检查所有卡牌是否都满足上述条件。

优化思路

直接枚举所有可能的 $g$ 并检查每张卡牌会超时（$n$ 最多 $10^6$，$a_i$ 最多 $5 \times 10^5$）。

关键优化：

• 我们只关心 $g$ 的候选值，它必须是某个 $a_i$ 或 $b_i$ 的因数。
• 但 $b_i$ 可能很大（最大 $2^{63}-1$），不能直接枚举所有因数。
• 观察：如果 $g$ 是最终答案，那么对于所有卡牌，$g$ 必须整除 $a_i$ 或 $b_i$。
• 我们可以反过来考虑：对于每个可能的 $g$（从大到小枚举），判断它是否满足条件。

算法步骤

1. 预处理
   对于每个 $a_i$，我们维护它与对应 $b_i$ 的 GCD，存入数组 a[x] 中。
   这里 a[x] 表示所有 $a_i = x$ 的卡牌中，$b_i$ 的 GCD。
   同时计算所有 $b_i$ 的 GCD 作为初始答案 res。

2. 构建 GCD ST 表
   对 a[1..maxx] 建立 ST 表，用于快速查询区间 GCD。

3. 从大到小枚举候选答案
   从 maxx 到 res+1 倒序枚举 $i$，检查 $i$ 是否可能是最终答案。
   检查方法：

   • 将区间 $[1, maxx]$ 按长度 $i$ 分段。
   • 对每一段 $[(j-1)\cdot i+1, j\cdot i - 1]$ 用 ST 表求 GCD。
   • 如果所有段的 GCD 都能被 $i$ 整除，则 $i$ 是可行解，输出并结束。

4. 输出结果
   如果没找到更大的，就输出 res。

算法标签

• 数论（GCD 性质）
• ST 表（区间 GCD 查询）
• 枚举优化（按倍数分段检查）

复杂度分析

• 预处理：$O(n + \max a_i)$
• ST 表构建：$O(\max a_i \log \max a_i)$
• 枚举检查：
  对于每个候选 $i$，检查次数是 $O(\frac{\max a_i}{i})$，总复杂度近似 $O(\max a_i \log \max a_i)$

总复杂度：$O(n + \max a_i \log \max a_i)$，在给定数据范围内可行。

代码关键点说明

// 核心检查逻辑
for (int i = maxx; i > res; i--) {
    ll ans = query(maxx / i * i + 1, maxx); // 最后一段
    for (int j = 1; j <= maxx / i && (ans % i == 0); j++)
        ans = gcd(ans, query((j - 1) * i + 1, j * i - 1));
    if (ans % i == 0) {
        cout << i;
        return 0;
    }
}

这里 query(l, r) 返回区间 $[l, r]$ 的 GCD。
我们按长度 $i$ 分段，如果所有段的 GCD 都能被 $i$ 整除，说明 $i$ 是可行解。

总结

这道题的关键在于：

1. 利用 GCD 的区间可合并性，用 ST 表快速查询。
2. 通过分段检查，避免对每个候选 $g$ 都扫描所有卡牌。
3. 从大到小枚举，一旦找到可行解立即输出。

这样既保证了正确性，又保证了高效性。