CF1780F Codeforces Round 846 (Div. 2) F. Three Chairs

标签：std 846 ch CF1780F res sum Three int include

https://codeforces.com/contest/1780/problem/F

计算

\[\sum_{i, j, k} [gcd(min(a_i, a_j, a_k), max(a_i, a_j, a_k)) = 1] \]

对 \(a_i\) 排序，则需计算

\[\sum_{i < k < j} [gcd(a_i, a_j) = 1] \]

将艾弗森括号展开成莫比乌斯函数形式，并枚举 \(k\)

\[\sum_k \sum_{i < k} \sum_{j > k} \sum_{d | a_i, d | a_j} \mu(d) \]

对于 \(k\)，后面的可以 \(O(1)\) 转移，即每次把 \(k - 1\) 对后面的贡献加上，\(k\) 对前面的贡献减去

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cstring>
#include <functional>

#define i64 long long

const int mod = 998244353, inf = 0x3f3f3f3f;

inline int read() {
    bool sym = 0; int res = 0; char ch = getchar();
    while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return sym ? -res : res;
}

int main() {
    int n; std::cin >> n;
    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) std::cin >> a[i];
    std::sort(a.begin() + 1, a.end());
    const int m = a[n];
    std::vector<int> mu(m + 1);
    mu[1] = 1;
    for (int i = 1; i <= m; i++) {
        for (int j = 2 * i; j <= m; j += i) {
            mu[j] -= mu[i];
        }
    }
    std::vector<std::vector<int>> div(m + 1);
    for (int i = 1; i <= m; i++) {
        for (int j = i; j <= m; j += i) {
            div[j].push_back(i);
        }
    }
    i64 ans = 0, cur = 0;
    std::vector<int> cl(m + 1), cr(m + 1);
    for (int i = 2; i <= n; i++) for (auto d : div[a[i]]) cr[d]++;
    for (int i = 2; i <= n; i++) {
        for (auto d : div[a[i - 1]]) cur += mu[d] * cr[d], cl[d]++;
        for (auto d : div[a[i]]) cur -= mu[d] * cl[d], cr[d]--;
        ans += cur;
    }
    std::cout << ans << "\n";
    return 0;
}

标签：std,846,ch,CF1780F,res,sum,Three,int,include
From： https://www.cnblogs.com/zrzring/p/CF1780F.html