DDOSvoid's Blog

2018-2019 Summer Petrozavodsk Camp, Oleksandr Kulkov Contest 2 B Yet Another Convolution

发表于 分类于
本文字数： 2.4k 阅读时长 ≈ 2 分钟

题目描述

https://codeforces.com/gym/102354/problem/B

简要题意：给定两个长度为 $n$ 的序列 $a_i,b_i$，求长度为 $n$ 的序列 $c_i$，其中 $c_k=\max_{gcd(i,j)=k}|a_i-b_j|$

$n\le 10^5,a_i,b_i\le 10^9$

Solution

我们考虑只统计 $a_i\le b_j$ 的答案，对于 $a_i>b_j$ 的答案我们只需要交换 $a$ 和 $b$ 重新求一次即可，另外我们只考虑 $gcd(i,j)=1$ 的情况，对于 $gcd(i,j)=d$ 的情况，我们只需要将 $i$ 和 $j$ 都除掉 $d$ 即可

首先我们将 $a$ 按升序排序，$b$ 按降序排序，那么我们考虑维护一个当前有效 $b$ 的集合 $S$，我们当前枚举到 $a_i$，我们考察集合 $S$ 中是否有与 $a_i$ 互质的 $b_j$，如果存在这么一个 $b_j$，那么集合内所有小于 $b_j$ 的数都没有用了，原因我们可以这样考虑对于我们接下来枚举到的 $a_{i’}>a_i$，其与 $b_{j’}<b_j$ 所组成的答案一定小于 $a_i$ 和 $b_j$ 组成的答案，那么我们的做法就是每次删除 $S$ 中与 $a_i$ 互质的数 $b_j$ 以及小于 $b_j$ 的数，注意到我们在一开始就完成了所有 $b_j$ 的插入，所以我们可以维护一个栈来代替集合，至于如何判断是否存在与 $a_i$ 互质的数，通过莫反，我们发现只需要 $cnt_d$，$cnt_d$ 表示 $S$ 中是 $d$ 的倍数的个数

时间复杂度 $O(n\log^2 n)$，似乎还有比较好想的 $O(n\log^3 n)$ 的二分做法

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
#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>
#include <stack>
#define maxn 100010
using namespace std;

int pri[maxn], cnt, mu[maxn]; bool isp[maxn]; vector<int> D[maxn];
void init_isp(int n) {
    mu[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (!isp[i]) pri[++cnt] = i, mu[i] = -1;
        for (int j = 1; j <= cnt && i * pri[j] <= n; ++j) {
            isp[i * pri[j]] = 1;
            if (i % pri[j] == 0) break;
            mu[i * pri[j]] = -mu[i]; 
        }
    }
    for (int i = 1; i <= n; ++i)
        for (int j = i; j <= n; j += i) D[j].push_back(i);
}

int n, a[maxn], b[maxn];
vector<int> A[maxn], B[maxn];

int ans[maxn];
void solve() {
    auto cmpa = [](const int &u, const int &v) { return a[u] < a[v]; };
    auto cmpb = [](const int &u, const int &v) { return b[u] < b[v]; };
    for (int t = 1; t <= n; ++t) {
        sort(A[t].begin(), A[t].end(), cmpa);
        sort(B[t].rbegin(), B[t].rend(), cmpb);
        stack<int> S; vector<int> cnt(n / t + 1);
        for (auto y : B[t]) {
            S.push(y);
            for (auto d : D[y / t]) ++cnt[d];
        }
        for (auto x : A[t]) {
            int res = 0; 
            for (auto d : D[x / t]) res += mu[d] * cnt[d];
            while (!S.empty() && (b[S.top()] <= a[x] || res)) {
                int y = S.top(); S.pop();
                for (auto d : D[y / t]) {
                    if (x / t % d == 0) res -= mu[d];
                    --cnt[d];
                } if (gcd(x / t, y / t) == 1) ans[t] = max(ans[t], b[y] - a[x]);
            }
        } 
    }
}

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n; init_isp(n); 
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) cin >> b[i];
    for (int i = 1; i <= n; ++i)
        for (int j = i; j <= n; j += i) A[i].push_back(j), B[i].push_back(j);
    solve(); for (int i = 1; i <= n; ++i) swap(a[i], b[i]); solve();
    for (int i = 1; i <= n; ++i) cout << ans[i] << " \n"[i == n];
    return 0;
}