[ABC215D] Coprime 2 题解-526互联

题意

给定数列 \(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;
}