「CF2131H」Sea, You & copriMe

    「CF2131H」Sea, You & copriMe

    CF2131H

    给出一个长度为 nn 的数组 aa,其中数组中的元素均为 1∼m1 \sim m 中的正整数。

    你需要找到四个不同的索引 p,q,r,sp, q, r, s,使得 gcd⁡(ap,aq)=1\gcd(a_p, a_q) = 1 且 gcd⁡(ar,as)=1\gcd(a_r, a_s) = 1。

    数据范围:4≤n≤2×1054 \leq n \leq 2 \times 10^5,1≤m≤1061 \leq m \leq 10^6,1≤ai≤m1 \leq a_i \leq m。

    时空限制:33s / 256256MiB。

    Solution

    考虑对于一个数 xx,判断序列中是否存在与 xx 互质的数,设 cnti\mathrm{cnt}_i 表示 ii 的出现次数。相当于是要求

    ∑i=1mcnti[gcd⁡(i,x)=1]=∑i=1mcnti∑d∣i,d∣xμ(d)=∑d∣xμ(d)∑d∣icnti\begin{aligned} & \sum\limits_{i = 1}^m \mathrm{cnt}_i [\gcd(i, x) = 1] \\ = & \sum\limits_{i = 1}^m \mathrm{cnt}_i \sum\limits_{d \mid i, d \mid x} \mu(d) \\ = & \sum\limits_{d \mid x} \mu(d) \sum\limits_{d \mid i} \mathrm{cnt}_i \end{aligned}

    首先可以求出一对 p,qp, q。从左向右遍历,假设当前遍历到 ii,首先 O(m)\mathcal{O}(\sqrt{m}) 地求出上式的值,若不为 00,则说明 1∼i−11 \sim i - 1 必定有一个与 aia_i 互质的数,暴力找出即可。否则,O(m)\mathcal{O}(\sqrt{m}) 地更新 ∑d∣icnti\sum_{d \mid i} \mathrm{cnt}_i 的值。

    然后将 p,qp, q 从序列中拿出来,继续尝试找出一对 r,sr, s(进行重复的事情)。

    若此时找不到 r,sr, s,那就有可能是因为 p,qp, q 绑定在了一起,导致其他数不能与 p,qp, q 进行匹配。所以剩余的一种情况是,一个数与 pp 匹配,还有一个数与 qq 匹配。遍历剩下的数,尝试匹配即可。

    时间复杂度 O(nm)\mathcal{O}(n\sqrt{m})。

    #include <bits/stdc++.h>
    
    using s64 = long long;
    using u64 = unsigned long long;
    
    /* 取 min */
    template <class T>
    inline void chmin(T &x, const T &y) {
        if (x > y) {
            x = y;
        }
    }
    /* 取 max */
    template <class T>
    inline void chmax(T &x, const T &y) {
        if (x < y) {
            x = y;
        }
    }
    
    /* ----- ----- ----- 正文 ----- ----- ----- */
    
    const int V = 1e6;
    const int MaxV = V + 10;
    
    int primeCount, prime[MaxV], fac[MaxV], miu[MaxV];
    std::vector<int> factor[MaxV];
    void sieve(const int &n) {
        miu[1] = 1;
        for (int i = 2; i <= n; i ++) {
            if (!fac[i]) {
                prime[++ primeCount] = i, fac[i] = i, miu[i] = -1;
            }
            for (int j = 1; j <= primeCount; j ++) {
                if (prime[j] > fac[i] || prime[j] > n / i) break;
                fac[i * prime[j]] = prime[j];
                miu[i * prime[j]] = miu[i] * (i % prime[j] ? -1 : 0);
            }
        }
    
        for (int i = 1; i <= n; i ++) {
            for (int j = i; j <= n; j += i) {
                factor[j].push_back(i);
            }
        }
    }
    
    const int N = 200100, M = 1000100;
    
    int n, m;
    int a[N], vis[N];
    
    int sum[M];
    
    std::pair<int, int> find() {
        for (int i = 1; i <= m; i ++) {
            sum[i] = 0;
        }
        for (int i = 1; i <= n; i ++) {
            if (vis[i]) {
                continue;
            }
            int b = 0;
            for (int d : factor[a[i]]) {
                b += miu[d] * sum[d], sum[d] ++;
            }
            if (b) {
                for (int j = 1; j < i; j ++) {
                    if (vis[j]) {
                        continue;
                    }
                    if (std::gcd(a[j], a[i]) == 1) {
                        vis[j] = vis[i] = 1;
                        return {j, i};
                    }
                }
            }
        }
    
        return {-1, -1};
    }
    
    void work() {
        std::cin >> n >> m;
    
        for (int i = 1; i <= n; i ++) {
            std::cin >> a[i], vis[i] = 0;
        }
    
        auto [p1, q1] = find();
        if (p1 == -1) {
            std::cout << 0 << '\n';
            return;
        }
    
        auto [p2, q2] = find();
        if (p2 != -1) {
            std::cout << p1 << ' ' << q1 << ' ' << p2 << ' ' << q2 << '\n';
            return;
        }
    
        int p = 0, q = 0;
        for (int i = 1; i <= n; i ++) {
            if (vis[i]) {
                continue;
            }
            int fp = std::gcd(a[i], a[p1]) == 1,
                fq = std::gcd(a[i], a[q1]) == 1;
    
            if (fp && q) {
                std::cout << i << ' ' << p1 << ' ' << q << ' ' << q1 << '\n';
                return;
            }
            if (fq && p) {
                std::cout << i << ' ' << q1 << ' ' << p << ' ' << p1 << '\n';
                return;
            }
    
            if (fp) p = i;
            if (fq) q = i;
        }
    
        std::cout << 0 << '\n';
    }
    
    int main() {
        std::ios::sync_with_stdio(0);
        std::cin.tie(0);
    
        sieve(V);
    
        int T;
        std::cin >> T;
        
        while (T --) {
            work();
        }
    
        return 0;
    }
    
    /**
     *  心中无女人
     *  比赛自然神
     *  模板第一页
     *  忘掉心上人
    **/