「CF2131H」Sea, You & copriMe

发表于 分类于 本文字数： 784 阅读时长 ≈ 3 分钟

Description

Link：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})。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#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;
}

/**
 *  心中无女人
 *  比赛自然神
 *  模板第一页
 *  忘掉心上人
**/