专栏文章

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

封封禁用户
P9401题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqas3vo
此快照首次捕获于
2025/12/04 01:45
3 个月前
此快照最后确认于
2025/12/04 01:45
3 个月前
查看原文
试机题。
果然是我太菜了。
注意到 bb 远大于 aa。所以全选 bb 可能比选任意个 aa 大，需要特判掉。
又发现 aa 的值域实在是特别小，所以选了 aa 的 gcd 也比较小。那么可以直接枚举答案，再判断是否成立。
然而直接朴素地查复杂度是 O(n2)\mathcal{O}(n ^ {2}) 的，于是搞一个 ST 表上来，预处理一下区间 gcd，倍增查询就是 O(log⁡n)\mathcal{O}(\log n) 的，合起来就是 O(nlog⁡n)\mathcal{O}(n \log n) 的。
然后需要注意一下常数。gcd 需要用 Binary GCD。
CPP
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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...