题意
给定 \(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\)）。
题解
设 \(\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)}
\]
下面考虑如何计算 \(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;
}