CF1575G GCD Festival 题解

标签：std right limits Festival 题解 sum varphi CF1575G left

题意

给定一个长度为 \(n\) 的正整数数列 \(a\)，求

\[\sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{n} \gcd\left(a_i, a_j\right) \times \gcd\left(i, j\right) \]

（\(1 \le n,a_i \le 10^5\)）。

题解

根据欧拉函数的性质，可以得出

\[n = \sum\limits_{d \mid n} \varphi(d) \]

该式也被称作欧拉反演。

下面开始化简算式

\[\begin{aligned} & \sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{n} \gcd\left(a_i, a_j\right) \times \gcd\left(i, j\right) \\ =& \sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{n} \gcd\left(a_i, a_j\right) \times \sum\limits_{d \mid \gcd\left(i, j\right)} \varphi(d) \\ =& \sum\limits_{d = 1}^{n} \varphi(d) \sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{n} \gcd\left(a_i, a_j\right) \left[d \mid \gcd\left(i, j\right)\right] \\ =& \sum\limits_{d = 1}^{n} \varphi(d) \sum\limits_{i = 1}^{n} \left[d \mid i\right]\sum\limits_{j = 1}^{n} \left[d \mid j\right]\gcd\left(a_i, a_j\right) \\ =& \sum\limits_{d = 1}^{n} \varphi(d) \sum\limits_{i = 1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j = 1}^{\lfloor\frac{n}{d}\rfloor} \gcd\left(a_{id}, a_{jd}\right) \\ =& \sum\limits_{d = 1}^{n} \varphi(d) \sum\limits_{i = 1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j = 1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{t \mid \gcd\left(a_{id}, a_{jd}\right)} \varphi(t) \\ =& \sum\limits_{d = 1}^{n} \varphi(d) \sum\limits_{t} \varphi(t) \sum\limits_{i = 1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j = 1}^{\lfloor\frac{n}{d}\rfloor}\left[t \mid \gcd\left(a_{id}, a_{jd}\right)\right] \\ =& \sum\limits_{d = 1}^{n} \varphi(d) \sum\limits_{t} \varphi(t) \sum\limits_{i = 1}^{\lfloor\frac{n}{d}\rfloor}\left[t \mid a_{id}\right]\sum\limits_{j = 1}^{\lfloor\frac{n}{d}\rfloor}\left[t \mid a_{jd}\right] \\ =& \sum\limits_{d = 1}^{n} \varphi(d) \sum\limits_{t} \varphi(t) \left(\sum\limits_{i = 1}^{\lfloor\frac{n}{d}\rfloor}\left[t \mid a_{id}\right]\right)^2 \\ \end{aligned}\]

我们先枚举 \(d\) 和 \(id\)，复杂度为 \(\mathcal{O}(n \ln n)\)。如果我们在枚举 \(t\) 时可以保证只枚举 \(a_{id}\) 的因子，那么总复杂度为 \(\mathcal{O}(n \ln n \max\limits_{i = 1}^{n} d(a_i))\)，其中 \(d(n) = \sum\limits_{i \mid n} 1\) 即 \(n\) 的约数个数，可以通过本题。

Code

//Codeforces - 1575G
#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;
typedef std::vector<bool> bitset;

constexpr valueType MOD = 1e9 + 7;

template<typename T1, typename T2, typename T3 = valueType>
void Inc(T1 &a, T2 b, const T3 &mod = MOD) {
    a = a + b;

    if (a >= mod)
        a -= mod;
}

template<typename T1, typename T2, typename T3 = valueType>
T1 mul(T1 a, T2 b, const T3 &mod = MOD) {
    return (long long) a * b % MOD;
}

class LineSieve {
public:
    typedef std::vector<valueType> container;

private:
    valueType size;
    bitset isPrime;
    container primeList, phi;
    ValueMatrix fact;

public:
    explicit LineSieve(valueType _size_) : size(_size_), isPrime(_size_ + 1, true), phi(_size_ + 1), fact(_size_ + 1) {
        phi[1] = 1;

        for (valueType i = 2; i <= size; ++i) {
            if (isPrime[i]) {
                primeList.push_back(i);
                phi[i] = i - 1;
            }

            for (auto const &iter: primeList) {
                valueType const t = i * iter;

                if (t > size)
                    break;

                isPrime[t] = false;

                if (i % iter == 0) {
                    phi[t] = phi[i] * iter;

                    break;
                } else {
                    phi[t] = phi[i] * (iter - 1);
                }
            }
        }

        for (valueType i = 1; i <= size; ++i) {
            for (valueType j = i; j <= size; j += i) {
                fact[j].push_back(i);
            }
        }
    }

    const container &Prime() const {
        return primeList;
    }

    valueType Phi(valueType x) const {
        if (x > size)
            throw std::range_error("Larger than Size.");

        if (x < 1)
            throw std::range_error("Too small.");

        return phi[x];
    }

    const container &Factor(valueType x) const {
        if (x > size)
            throw std::range_error("Larger than Size.");

        if (x < 1)
            throw std::range_error("Too small.");

        return fact[x];
    }
};

constexpr valueType V = 1e5 + 5;

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

    LineSieve const sieve(V);

    valueType N;

    std::cin >> N;

    ValueVector source(N + 1, 0);

    for (valueType i = 1; i <= N; ++i)
        std::cin >> source[i];

    valueType ans = 0;
    ValueVector count(V, 0);

    for (valueType d = 1; d <= N; ++d) {
        for (valueType i = d; i <= N; i += d)
            for (auto const &iter: sieve.Factor(source[i]))
                ++count[iter];

        valueType sum = 0;

        for (valueType i = d; i <= N; i += d) {
            for (auto const &iter: sieve.Factor(source[i])) {
                if (count[iter] > 0) {
                    Inc(sum, mul(mul(count[iter], count[iter]), sieve.Phi(iter)));

                    count[iter] = 0;
                }
            }
        }

        Inc(ans, mul(sum, sieve.Phi(d)));
    }

    std::cout << ans << std::endl;


    return 0;
}

标签：std,right,limits,Festival,题解,sum,varphi,CF1575G,left
From： https://www.cnblogs.com/User-Unauthorized/p/solution-CF1575G.html