Luogu5221 Product

Description

给定 $n$ ，求下式的值

$\prod_{i=1}^{n}\prod_{j=1}^{n}\frac{\text{lcm}(i,j)}{\text{gcd}(i,j)}$

Solution

分享两种做法。
第一种是类似于 $\sum$ 时的做法：

$\begin{aligned} \prod_{i=1}^{n}\prod_{j=1}^{n}\frac{\text{lcm}(i,j)}{\text{gcd}(i,j)} &= \prod_{i=1}^{n}\prod_{j=1}^{n}ij\prod_{d=1}^{n}d^{-2[\gcd(i,j)=d]}\\ &=(n!)^{2n}\prod_{d=1}^{n}d^{-2\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}[\gcd(i,j)=d]} \end{aligned}$

指数上的东西可以转化成 $\varphi$ 。复杂度 $\mathcal{O}(n\log_2n)$ 。

第二种做法需要用到一个奇怪形式的函数的性质

$\begin{aligned} \prod_{i=1}^{n}\prod_{j=1}^{n}\frac{\text{lcm}(i,j)}{\text{gcd}(i,j)} &= \prod_{i=1}^{n}\prod_{j=1}^{n}ij(\prod_{d=1}^{n}d^{[\gcd(i,j)=d]})^{-2}\\ &= (n!)^{2n}(\prod_{d=1}^{n}d^{\sum\limits_{t=1}^{n}\mu(t)(\frac{n}{td})^2})^{-2} &=(n!)^{2n}(\prod_{T=1}^{n}(\prod_{d|T}(d^{\mu(\frac{T}{d})})^{(\frac{n}{T})^2})^{-2} \end{aligned}$

注意一下内层的东西

$f(T)=\prod_{d|T}d^{\mu(\frac{T}{d})}$

这个函数是可以欧拉筛筛出来的。

一般拿到一个函数时，我们先证明其是积性函数，再通过 质数 $\rightarrow$ 质数幂 $\rightarrow$ 合数 的顺序逐步分析怎么筛。当然，如果函数不是积性函数，但很有特点，也可以筛。

先考虑质数：$f(p)=p$ 。
再考虑质数幂：$f(p^k)=p^k\times \frac{1}{p^{k-1}} = p$ 。
考虑合数：由于幂次中只有莫比乌斯函数，我们考虑 分开计算每个质数的贡献 。假设合数中有质数 $p^k$ ，那么贡献一定是 $(p^k)^C\times (\frac{1}{p^{k-1}})^C$ ，其中 $C$ 是其他质因子对于 $p^k$ 的贡献。考虑除了 $p$ 之外有 k 个质因数，那么有

$C=\sum_{i=0}^{k}(-1)^k\binom{k}{i} = [k=0]$

所以每个质数的贡献都是 $1$ ，所有合数的函数值恒为 $1$ 。
于是这个式子我们也可以快速算，复杂度 $\mathcal{O}(n\log_2n)$。