[ABC215D] Coprime 2 题解

· · 题解

题意

给定数列 A_N 和一个正整数 M，求出所有的 1 \le k \le M 满足 \forall i \in \left[1,N\right],\gcd(k, A_i) = 1。

题解

本题存在线性复杂度算法。

记 \operatorname{lpf}(n) = [1 < n] \min\{p : p \mid n\} + [1 = n]，即 n 的最小质因数。特别地，n=1 时，其值为 1。

考虑线性筛筛出合数的过程，合数 n 会被 \dfrac{n}{\operatorname{lpf}(n)} 筛掉，从 n 向其连边，可以发现最终会形成一棵树。建树过程的复杂度为 \mathcal{O}(N)，接下来我们在这棵树上进行操作。

首先对数列 A_n 的每个元素 A_i，在这棵树上的对应节点打上一个 tag，然后我们暴力向上跳，给路过的每个节点和边打上 tag，其中给边 \left(u, pa_u\right) 打 tag 直接给 \operatorname{lpf}(u) 对应的节点打上 tag 即可，如果我们跳到已经打过 tag 的点那么就停止向上跳。其中我们是通过给边打 tag 来处理出在这个数列中所有作为质因子出现的质数，给节点打 tag 是为了避免多余的处理，可以看出每条边最多被处理一次，所以这部分复杂度也是线性。

现在我们已经处理出了所有在这个数列中出现的质因子，易证符合题目条件的 k 就是不含有这其中任意一个质因子的数，所以我们下面考虑将 tag 下方，只要一条边对应的质数被打上了 tag，那么所有到根节点路径上有这条边的数都含有该质因子，所以我们考虑从上而下的下方 tag，同时可以断定 pa_u < u，即 u 节点的父节点值一定比 u 小，所以从小到大遍历节点，考虑父亲节点是否打上 tag 和 当前节点与父亲节点相连的边是否打上 tag 即可，同上面一样，给节点打 tag 一是为了记录答案，二是可以减少不必要的重复遍历，这部分中每条边最多被处理一次，所以这部分复杂度也是线性。总复杂度也为线性。

考虑到本题数据过水，不能体现出线性算法的效率，所以造了一个加强版：T358758。

Code

//A
#include <bits/stdc++.h>

typedef int valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<bool> bitset;

constexpr valueType MAX = 1e5 + 5;

int main() {
    std::ios_base::sync_with_stdio(false);

    valueType N, M;

    std::cin >> N >> M;

    ValueVector source(N);

    for (auto &iter: source)
        std::cin >> iter;

    ValueVector father(MAX + 1, 1);

    bitset tag(MAX + 1, true);

    ValueVector primeList;

    primeList.reserve(std::ceil((long double) MAX / std::log((long double) MAX)));

    for (valueType i = 2; i <= MAX; ++i) {
        if (__builtin_expect(tag[i], false)) {
            father[i] = 1;
            primeList.emplace_back(i);
        }

        for (auto const &iter: primeList) {
            valueType const t = iter * i;

            if (t > MAX)
                break;

            tag[t] = false;
            father[t] = i;

            if (__builtin_expect(i % iter == 0, false))
                break;
        }
    }

    std::fill(tag.begin(), tag.end(), false);

    typedef std::function<void(valueType)> TagFunction;

    TagFunction solve = [&father, &tag](valueType n) {
        while (n > 1 && !tag[n]) {
            tag[n] = true;
            tag[n / father[n]] = true;
            n = father[n];
        }
    };

    for (auto const &iter: source)
        solve(iter);

    tag[1] = false;
    for (valueType i = 2; i <= MAX; ++i)
        tag[i] = tag[i] || (tag[father[i]] || tag[i / father[i]]);

    ValueVector result;

    result.reserve(M);

    result.push_back(1);

    for (valueType i = 2; i <= M; ++i)
        if (!tag[i])
            result.push_back(i);

    std::cout << result.size() << '\n';

    for (auto const &iter: result)
        std::cout << iter << '\n';

    std::cout << std::flush;

    return 0;
}