P5518 [MtOI2019]幽灵乐团 / 莫比乌斯反演基础练习题
记 $s _ n = \sum _ {i = 1} ^ n i $ 。
Type 0
$\mathrm {lcm} (i, j) = \frac {ij} {gcd(i, j)}$ 。将分子分母每个部分分开计算，$X(A, B, C) = \prod _ {i = 1} ^ A \prod _ {j = 1} ^ B \prod _ {k = 1} ^ C i$ ，$Y(A, B, C) = \prod _ {i = 1} ^ A \prod _ {j = 1} ^ B \prod _ {k = 1} ^ C (i, j)$ 。那么答案为 $\frac {X(A, B, C) X(B, A, C)} {Y(A, B, C) Y(A, C, B)}$ 。
$$X(A, B, C) = (A!) ^ {BC}$$
$$
\begin {aligned}
Y(A, B, C) & = \prod _ {i = 1} ^ A \prod _ {j = 1} ^ B \prod _ {k = 1} ^ C (i, j)\\
& = (\prod _ {i = 1} ^ A \prod _ {j = 1} ^ B (i, j)) ^ C \\
& = (\prod _ {d = 1} ^ n \prod _ {i = 1} ^ A \prod _ {j = 1} ^ B d ^ {[(i, j) = d]}) ^ C \\
& = (\prod _ {d = 1} ^ n d ^ {\sum _ {i = 1} ^ A \sum _ {j = 1} ^ B [(i, j) = d]}) ^ C \\
& = (\prod _ {d = 1} ^ n d ^ {\sum _ {k = 1} ^ {\lfloor \frac n d \rfloor } \mu(k) {\lfloor \frac A {kd} \rfloor }{\lfloor \frac B {kd} \rfloor }}) ^ C \\
& = (\prod _ {T = 1} ^ n (\prod _ {d | T} d ^ {\mu(\frac T d )}) ^ {\lfloor \frac A T \rfloor \lfloor \frac B T \rfloor}) ^ C
\end {aligned}
$$
其中 $\prod _ {d | T} d ^ {\mu(\frac T d )}$ 可以用 $n \ln n$ 时间预处理，做前缀积，可以数论分块。
Type 1
$$X(A, B, C) = \prod _ {i = 1} ^ A \prod _ {j = 1} ^ B \prod _ {k = 1} ^ C i ^ {ijk} = (\prod _ {i = 1} ^ A i ^ i) ^ {s_ B s _ C} $$
$$
\begin {aligned}
Y(A, B, C) & = \prod _ {i = 1} ^ A \prod _ {j = 1} ^ B \prod _ {k = 1} ^ C (i, j) ^ {ijk} \\
& = (\prod _ {i = 1} ^ A \prod _ {j = 1} ^ B (i, j) ^ {ij}) ^ {s _ C} \\
& = (\prod _ {d = 1} ^ n \prod _ {i = 1} ^ A \prod _ {j = 1} ^ B d ^ {ij[(i, j) = d]}) ^ {s _ C} \\
& = (\prod _ {d = 1} ^ n d ^ {\sum _ {i = 1} ^ A \sum _ {j = 1} ^ B ij[(i, j) = d]}) ^ {s _ C} \\
& = (\prod _ {d = 1} ^ n d ^ {\sum _ {k = 1} ^ {\lfloor \frac n d \rfloor } \mu(k) d ^ 2 k ^ 2{s _ {\lfloor \frac A {kd} \rfloor} }{s _ {\lfloor \frac B {kd} \rfloor} }}) ^ {s _ C} \\
& = (\prod _ {T = 1} ^ n (\prod _ {d | T} d ^ {\mu(\frac T d ) T ^ 2}) ^ { s _ {\lfloor \frac A {kd} \rfloor} s _ {\lfloor \frac B {kd} \rfloor} }) ^ {s _ C}
\end {aligned}
$$
其中 $\prod _ {d | T} d ^ {\mu(\frac T d ) T ^ 2}$ 可以用 $n \ln n$ 时间预处理，做前缀积，可以数论分块。
Type 2
$$
\begin {aligned}
\prod_{i = 1}^A \prod_{j = 1}^B \prod_{k = 1}^C (\frac{\mathrm{lcm}(i, j)}{(i, k)} )^{(i, j, k)} = \prod _ {d = 1} ^ n (\prod _ {i = 1} ^ {\lfloor \frac A d \rfloor}\prod _ {i = 1} ^ {\lfloor \frac B d \rfloor} \prod _ {k = 1} ^ { \lfloor \frac C d \rfloor} \frac{\mathrm{lcm}(i, j)}{(i, k)} ) ^ {\varphi (d)}
\end {aligned}
$$
中间部分为 Type 0 答案，数论分块套数论分块，复杂度 $O(n ^ {\frac 3 4} \log ^ 2 p)$ 。
查看代码
1 |
|