P7486 「Stoi2031」彩虹题解

User-Unauthorized / 2023-08-22 / 原文

题意

给定 \(l, r\)，求

\[\prod\limits_{i = l}^{r} \prod\limits_{j = l}^{r} \operatorname{lcm}\left(i, j\right)^{\operatorname{lcm}\left(i, j\right)} \bmod 32465177 \]

（\(1 \le l \le r \le 10^6, 1 \le T \le 10\)）。

题解

设 \(\operatorname{F}(n, m) = \prod\limits_{i = 1}^{n} \prod\limits_{j = 1}^{m} \operatorname{lcm}\left(i, j\right)^{\operatorname{lcm}\left(i, j\right)}\)，那么根据容斥可得

\[\text{Ans} = \dfrac{\operatorname{F}(r, r) \times \operatorname{F}(l - 1, l - 1)}{\operatorname{F}(l - 1, r) \times \operatorname{F}(r, l - 1)} \]

下面考虑如何计算 \(\operatorname{F}(n, m)\)，注意，在下文的推导中，假定 \(n \le m\)。

\[\begin{aligned} \operatorname{F}(n, m) &= \prod\limits_{i = 1}^{n} \prod\limits_{j = 1}^{m} \operatorname{lcm}\left(i, j\right)^{\operatorname{lcm}\left(i, j\right)} \\ &= \prod\limits_{i = 1}^{n} \prod\limits_{j = 1}^{m} \left(\dfrac{i \cdot j}{\gcd\left(i, j\right)}\right) ^{\frac{i \cdot j}{\gcd\left(i, j\right)}} \\ &= \prod\limits_{d = 1}^{n}\prod\limits_{i = 1}^{n} \prod\limits_{j = 1}^{m} \left(\dfrac{i \cdot j}{d}\right) ^{\left[\gcd\left(i, j\right) = d\right]\frac{i \cdot j}{d}} \\ &= \prod\limits_{d = 1}^{n}\prod\limits_{i = 1}^{n} \prod\limits_{j = 1}^{m} \left(d \dfrac{i}{d} \dfrac{j}{d}\right) ^{\left[\gcd\left(i, j\right) = d\right]d \frac{i}{d} \frac{j}{d}} \\ &= \prod\limits_{d = 1}^{n}\prod\limits_{i = 1}^{\left\lfloor\frac{n}{d}\right\rfloor} \prod\limits_{j = 1}^{\left\lfloor\frac{m}{d}\right\rfloor} \left(ijd\right)^{\left[\gcd\left(i, j\right) = 1\right]ijd} \\ &= \prod\limits_{d = 1}^{n}\prod\limits_{i = 1}^{\left\lfloor\frac{n}{d}\right\rfloor} \prod\limits_{j = 1}^{\left\lfloor\frac{m}{d}\right\rfloor} \left(ijd\right) ^{\sum\limits_{t \mid \gcd\left(i, j\right)} \mu\left(t\right)ijd} \\ &= \prod\limits_{d = 1}^{n} \prod\limits_{t = 1}^{\frac{n}{d}} \prod\limits_{i = 1}^{\left\lfloor\frac{n}{d}\right\rfloor} \prod\limits_{j = 1}^{\left\lfloor\frac{m}{d}\right\rfloor} \left(ijd\right) ^{\left[t \mid i \land t \mid j\right] \mu\left(t\right)ijd} \\ &= \prod\limits_{d = 1}^{n} \prod\limits_{t = 1}^{\frac{n}{d}} \prod\limits_{i = 1}^{\left\lfloor\frac{n}{dt}\right\rfloor} \prod\limits_{j = 1}^{\left\lfloor\frac{m}{dt}\right\rfloor} \left(ijdt^2\right) ^{\mu\left(t\right)ijdt^2} \\ &= \prod\limits_{T = 1}^{n} \prod\limits_{p \mid T} \prod\limits_{i = 1}^{\left\lfloor\frac{n}{T}\right\rfloor} \prod\limits_{j = 1}^{\left\lfloor\frac{m}{T}\right\rfloor} \left(ijTp\right) ^{ijTp\mu\left(p\right)} \\ \end{aligned}\]

下面考虑计算该式。

设 \(\operatorname{w}(n) = \prod\limits_{i = 1}^{n} i^i, \operatorname{S}(n) = \sum\limits_{i = 1}^{n} i = \dfrac{i \left(i + 1\right)}{2}, \operatorname{G}(n, m) = \prod\limits_{i = 1}^{n}\prod\limits_{j = 1}^{m} \left(ij\right)^{ij}\)，那么可得

\[\begin{aligned} \operatorname{G}(n, m) &= \prod\limits_{i = 1}^{n} \prod\limits_{j = 1}^{m} \left(ij\right)^{ij} \\ &= \prod\limits_{i = 1}^{n} \prod\limits_{j = 1}^{m} i^{ij} \times \prod\limits_{i = 1}^{n} \prod\limits_{j = 1}^{m} j^{ij} \\ &= \prod\limits_{i = 1}^{n} \prod\limits_{j = 1}^{m} \left(i^i\right)^j \times \prod\limits_{i = 1}^{n} \prod\limits_{j = 1}^{m} \left(j^j\right)^i \\ &= \operatorname{w}(n)^{\operatorname{S}(m)} \times \operatorname{w}(m)^{\operatorname{S}(n)} \end{aligned}\]

代入原式可得

\[\begin{aligned} \operatorname{F}\left(n, m\right) &= \prod\limits_{T = 1}^{n} \prod\limits_{p \mid T} \prod\limits_{i = 1}^{\left\lfloor\frac{n}{T}\right\rfloor} \prod\limits_{j = 1}^{\left\lfloor\frac{m}{T}\right\rfloor} \left(ijTp\right) ^{ijTp\mu\left(p\right)} \\ &= \prod\limits_{T = 1}^{n} \prod\limits_{p \mid T} \prod\limits_{i = 1}^{\left\lfloor\frac{n}{T}\right\rfloor} \prod\limits_{j = 1}^{\left\lfloor\frac{m}{T}\right\rfloor} \left(\operatorname{G}\left(\dfrac{n}{d}, \dfrac{m}{d}\right) \times \left(Tp\right)^{ij}\right) ^{Tp\mu\left(p\right)} \\ &= \prod\limits_{T = 1}^{n} \prod\limits_{p \mid T} \prod\limits_{i = 1}^{\left\lfloor\frac{n}{T}\right\rfloor} \prod\limits_{j = 1}^{\left\lfloor\frac{m}{T}\right\rfloor} \operatorname{G}\left(\dfrac{n}{d}, \dfrac{m}{d}\right)^{Tp\mu\left(p\right)} \times \left(Tp\right)^{ijTp\mu\left(p\right)} \\ &= \prod\limits_{T = 1}^{n} \prod\limits_{p \mid T} \prod\limits_{i = 1}^{\left\lfloor\frac{n}{T}\right\rfloor} \prod\limits_{j = 1}^{\left\lfloor\frac{m}{T}\right\rfloor} \operatorname{G}\left(\dfrac{n}{d}, \dfrac{m}{d}\right)^{Tp\mu\left(p\right)} \times \left(\left(Tp\right)^{Tp\mu\left(p\right)}\right)^{ij} \\ &= \prod\limits_{T = 1}^{n} \prod\limits_{p \mid T} \operatorname{G}\left(\dfrac{n}{d}, \dfrac{m}{d}\right)^{Tp\mu\left(p\right)} \times \left(\left(Tp\right)^{Tp\mu\left(p\right)}\right)^{\operatorname{S}\left(n\right) \operatorname{S}\left(m\right)} \\ \end{aligned}\]

记 \(\displaystyle \operatorname{g}(n) = n \sum\limits_{p \mid n} p\mu\left(p\right), \operatorname{h}(n) = \prod\limits_{p \mid n} \left(np\right)^{n p \mu\left(p\right)} = \left(\prod\limits_{p \mid n} \left(np\right)^{p \mu\left(p\right)} \right)^n\)，那么可得

\[\operatorname{F}\left(n, m\right) = \prod\limits_{T = 1}^{n} \operatorname{G}\left(\dfrac{n}{d}, \dfrac{m}{d}\right)^{g(T)} \times \operatorname{h}(T)^{\operatorname{S}\left(n\right) \operatorname{S}\left(m\right)}\]

预处理出 \(g\) 的前缀和，\(h\) 的前缀积再利用整除分块即可通过本题。

直接枚举倍数预处理两个函数，时间复杂度 \(\mathcal{O}(n \ln n \log n + T\sqrt{n}\log n)\)，可以通过本题。

Code

//Luogu - P7486
#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;

constexpr valueType MOD = 32465177;

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>
void Dec(T1 &a, T2 b, const T3 &mod = MOD) {
    a = a - b;

    if (a < 0)
        a += mod;
}

template<typename T1, typename T2, typename T3 = valueType>
T1 sum(T1 a, T2 b, const T3 &mod = MOD) {
    return a + b >= mod ? a + b - mod : a + b;
}

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;
    typedef std::vector<bool> bitset;

private:
    valueType N;
    bitset isPrime;
    container primeList;
    container mobius, g, h, w;

public:
    explicit LineSieve(valueType _size_) : N(_size_), isPrime(N + 1, true), mobius(N + 1), g(N + 1, 0), h(N + 1, 1),
                                           w(N + 1, 1) {
        primeList.reserve((size_t) std::ceil(std::log((long double) (_size_ + 1))));
        mobius[1] = 1;
        for (valueType i = 2; i <= N; ++i) {
            if (isPrime[i]) {
                primeList.push_back(i);
                mobius[i] = -1;
            }

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

                if (t > N)
                    break;

                isPrime[t] = false;

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

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

        for (valueType i = 1; i <= N; ++i) {
            for (valueType j = i; j <= N; j += i) {
                Inc(g[j], mul(i, mobius[i] + (MOD - 1), MOD - 1), MOD - 1);
                Mul(h[j], pow(mul(i, j), mul(mobius[i] + (MOD - 1), i, MOD - 1), MOD));
            }

            Mul(g[i], i, MOD - 1);

            h[i] = pow(h[i], i);

            Mul(h[i], h[i - 1]);
            Inc(g[i], g[i - 1], MOD - 1);

            w[i] = pow(i, i);
            Mul(w[i], w[i - 1]);
        }
    }

    valueType G(valueType n) const {
        return g[n];
    }

    valueType H(valueType n) const {
        return h[n];
    }

    valueType W(valueType n) const {
        return w[n];
    }
};

class Inverse {
private:
    valueType size, mod;

    ValueVector data;

public:
    explicit Inverse(valueType N, valueType mod = MOD) : size(N), mod(mod), data(N + 1, 0) {
        data[1] = 1;

        for (valueType i = 2; i <= N; ++i)
            data[i] = mul((mod - mod / i), data[mod % i], mod);
    }

    valueType operator()(valueType i) const {
        i %= mod;

        if (i <= size)
            return data[i];

        return mul((mod - mod / i), operator()(mod % i), mod);
    }
};

constexpr valueType V = 1e6 + 5;

LineSieve sieve(V);
Inverse Inv(V, MOD);


valueType S(valueType n, valueType mod = MOD) {
    return (long long) n * (n + 1) / 2 % mod;
}

valueType G(valueType n, valueType m) {
    return mul(pow(sieve.W(n), S(m, MOD - 1)), pow(sieve.W(m), S(n, MOD - 1)));
}

valueType F(valueType n, valueType m) {
    if (n > m)
        std::swap(n, m);

    valueType result = 1;

    valueType l = 1, r;

    while (l <= n) {
        r = std::min(n / (n / l), m / (m / l));

        Mul(result, pow(G(n / l, m / l), sub(sieve.G(r), sieve.G(l - 1), MOD - 1)));

        Mul(result, pow(mul(sieve.H(r), Inv(sieve.H(l - 1))), mul(S(n / l, MOD - 1), S(m / l, MOD - 1), MOD - 1)));

        l = r + 1;
    }

    return result;
}

int main() {
    valueType T, N;

    std::cin >> T >> N;

    for (valueType i = 0; i < T; ++i) {
        valueType l, r;

        std::cin >> l >> r;

        valueType const result = mul(mul(F(l - 1, l - 1), F(r, r)), Inv(mul(F(l - 1, r), F(r, l - 1))));

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

    return 0;
}