CF915G Coprime Arrays 题解

标签：lfloor right Arrays 题解 rfloor Coprime dfrac mod left

题意

给定 \(n, k\)，对于所有的 \(m \in \left[1, k\right]\)，求长度为 \(n\)，值域为 \(\left[1,m \right]\) 且最大公约数为 \(1\) 的序列种数，对 \(10^9 + 7\) 取模。

（\(1 \le n,k \le 2 \times 10^6\)）。

题解

设 \(f(d, m)\) 表示长度为 \(n\)，值域为 \(\left[1,m \right]\) 且最大公约数为 \(1\) 的序列种数，\(g(d, m)\) 表示长度为 \(n\)，值域为 \(\left[1,m \right]\) 且序列元素均为 \(d\) 的倍数即最大公约数为 \(d\) 的倍数的序列种数，那么有

\[\begin{aligned} g(d, m) &= \sum\limits_{d \mid h} f(h, m) \\ f(d, m) &= \sum\limits_{d \mid h} \mu\left(\dfrac{h}{d}\right) g(h, m) \end{aligned}\]

考虑计算 \(g(d, m)\)，发现

\[g(d, m) = \left\lfloor\dfrac{m}{d}\right\rfloor^n \]

综上，可得

\[f(1, m) = \sum\limits_{i = 1}^{m} \mu\left(i\right)\left\lfloor\dfrac{m}{i}\right\rfloor^n \]

现在我们得到了答案的计算式，但是若对于每个 \(m\) 应用整除分块计算，复杂度为 \(\mathcal{O}(k \sqrt{k} \log n)\)，若使用线性筛预处理出幂函数，那么复杂度为 \(\mathcal{O}(k \sqrt{k})\)，均无法通过本题。

故考虑在 \(f(1, m - 1)\) 的基础上计算 \(f(1, m)\)，考虑 \(f(1, m)\) 较 \(f(1, m - 1)\) 的差值均为 \(\left\lfloor\dfrac{m}{i}\right\rfloor\) 的改变引起的，而对于每个 \(i\)，只有 \(m\) 增大为 \(i\) 的倍数时该值才会改变，故答案共会改变 \(\mathcal{O}(k \ln k)\) 次。形式化的，有

\[\begin{aligned} f(1, m) &= f(1, m - 1) + \left(f(1, m) - f(1, m - 1)\right) \\ &= f(1, m - 1) + \left(\sum\limits_{i = 1}^{m} \mu\left(i\right)\left\lfloor\dfrac{m}{i}\right\rfloor^n - \sum\limits_{i = 1}^{m - 1} \mu\left(i\right)\left\lfloor\dfrac{m - 1}{i}\right\rfloor^n\right) \\ &= f(1, m - 1) + \sum\limits_{i = 1}^{m}\mu\left(i\right)\times\left(\left\lfloor\dfrac{m}{i}\right\rfloor^n - \left(\left\lfloor\dfrac{m}{i}\right\rfloor - 1\right)^n\right) \end{aligned}\]

而 \(\left\lfloor\dfrac{m}{i}\right\rfloor^n - \left(\left\lfloor\dfrac{m}{i}\right\rfloor - 1\right)^n\) 的取值只有 \(i \mid m\) 时才不为 \(0\)，故上式后半部分在 \(m\) 取遍 \(\left[1, k\right]\) 时产生贡献的次数共为 \(\mathcal{O}(k \ln k)\) 次。

对于每个数，预处理其因子，在 \(m\) 增长后，对于当前 \(m\) 的所有因子 \(i\)，\(\left\lfloor\dfrac{m}{i}\right\rfloor\) 的值均会增长 \(1\)，将答案累加 \(\mu\left(i\right)\times\left(\left\lfloor\dfrac{m}{i}\right\rfloor^n - \left(\left\lfloor\dfrac{m}{i}\right\rfloor - 1\right)^n\right)\) 即可。

使用线性筛预处理出幂函数，在 \(n,k\) 同阶的情况下，总复杂度为 \(\mathcal{O}(n \log n)\)，可以通过本题。

Code

#include <bits/stdc++.h>

typedef int 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 sub(T1 a, T2 b, const T3 &mod = MOD) {
    return a - b < 0 ? a - b + mod : a - b;
}

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

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

template<typename T1, typename T2, typename T3 = valueType>
T1 pow(T1 a, T2 b, const T3 &mod = MOD) {
    T1 result = 1;

    while (b > 0) {
        if (b & 1)
            Mul(result, a, mod);

        Mul(a, a, mod);
        b = b >> 1;
    }

    return result;
}

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

private:
    valueType N, M;
    container prime;
    bitset isPrime;
    container Mobius, Power;
    ValueMatrix Factor;

public:
    LineSieve(valueType n, valueType m) : N(n), M(m), prime(), isPrime(n + 1, true), Mobius(n + 1, 1), Factor(n + 1),
                                          Power(n + 1, 1) {
        isPrime[0] = isPrime[1] = false;
        Mobius[1] = 1;
        Power[0] = 0;
        Power[1] = 1;

        for (valueType i = 2; i <= N; ++i) {
            if (isPrime[i]) {
                prime.push_back(i);

                Mobius[i] = -1;

                Power[i] = ::pow(i, M);
            }

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

                if (t > N)
                    break;

                isPrime[t] = false;

                Power[t] = mul(Power[i], Power[iter]);

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

                    break;
                } else {
                    Mobius[t] = -Mobius[i];
                }
            }

            if (Mobius[i] < 0)
                Mobius[i] += MOD;
        }

        for (valueType i = 1; i <= N; ++i)
            for (valueType j = i; j <= N; j += i)
                Factor[j].push_back(i);
    }

    valueType operator()(valueType n) const {
        return Mobius[n];
    }

    valueType pow(valueType n) const {
        return Power[n];
    }

    const ValueVector &fact(valueType n) const {
        return Factor[n];
    }
};

int main() {
    valueType N, K;

    std::cin >> N >> K;

    LineSieve const sieve(K, N);

    ValueVector ans(K + 1, 0);

    for (valueType i = 1; i <= K; ++i) {
        ans[i] = ans[i - 1];

        for (auto const &iter: sieve.fact(i))
            Inc(ans[i], mul(sieve(iter), sub(sieve.pow(i / iter), sieve.pow(i / iter - 1))));
    }

    valueType result = 0;

    for (valueType i = 1; i <= K; ++i)
        Inc(result, ans[i] ^ i);

    std::cout << result << std::endl;
}

标签：lfloor,right,Arrays,题解,rfloor,Coprime,dfrac,mod,left
From： https://www.cnblogs.com/User-Unauthorized/p/solution-CF915G.html