题解：P9401 [POI 2020/2021 R3] Kolekcjoner Bajtemonów 2

YDMaYi · 2025-02-09 15:47:02 · 题解

试机题。

果然是我太菜了。

注意到 b 远大于 a。所以全选 b 可能比选任意个 a 大，需要特判掉。

又发现 a 的值域实在是特别小，所以选了 a 的 gcd 也比较小。那么可以直接枚举答案，再判断是否成立。

然而直接朴素地查复杂度是 \mathcal{O}(n ^ {2}) 的，于是搞一个 ST 表上来，预处理一下区间 gcd，倍增查询就是 \mathcal{O}(\log n) 的，合起来就是 \mathcal{O}(n \log n) 的。

然后需要注意一下常数。gcd 需要用 Binary GCD。

int gcd(int a, int b) {
    int az = __builtin_ctz(a);
    int bz = __builtin_ctz(b);
    int z = min(az, bz);
    b >>= bz;
    while (a) {
        a >>= az;
        int diff = a - b;
        az = __builtin_ctz(diff);
        b = min(a, b), a = abs(diff);
    }
    return b << z;
}