# ShanLunjiaJian的blog

### 一道可能是nowcoder上的题 题解

posted on 2021-04-06 19:33:35 | under 题解 |

$$\prod_{a}\mathrm{lcm}(a_i)^{\gcd(a_i)}$$

。$n\leq 10^9$，$m\leq 2\times 10^5$，膜质数。

\begin{aligned} &\prod_{a}\mathrm{lcm}(a_i)^{\gcd(a_i)}\\ =&\prod_{d}\prod_{d\vert a}\mathrm{lcm}(a_i)^{\varphi(d)}\\ =&\prod_{d}d^{\lfloor\frac{m}{d}\rfloor^n}\left(\prod_{a\in[1,\lfloor\frac{m}{d}\rfloor]}\mathrm{lcm}(a_i)\right)^d \end{aligned}

\begin{aligned} &\prod_{a}\mathrm{lcm}(a_i)^{\gcd(a_i)}\\ =&\prod_{d}\prod_{d\vert a}\mathrm{lcm}(a_i)^{\varphi(d)}\\ =&\prod_{d}d^{\lfloor\frac{m}{d}\rfloor^n}\left(\prod_{a\in[1,\lfloor\frac{m}{d}\rfloor]}\mathrm{lcm}(a_i)\right)^d\\ =&\prod_{d}d^{\lfloor\frac{m}{d}\rfloor^n}\left(f(\lfloor\frac{m}{d}\rfloor)\right)^d\\ f(m)=&\prod_{p^e}p^{m^n-(m-\lfloor\frac{m}{p^{e}}\rfloor)^n} \end{aligned}

upd : 我消掉了!但是不知道对不对。

\begin{aligned} &\prod_{S}\mathrm{lcm}(S)^{\gcd(S)}\\ =&\prod_{S}\prod_{T\neq\varnothing,T\subseteq S}\gcd(T)^{(-1)^{\vert T\vert+1}\gcd(S)}\\ =&\prod_{S}\prod_{T\neq\varnothing,T\subseteq S}\gcd(T)^{(-1)^{\vert T\vert+1}\sum_{d\vert S}\varphi(d)}\\ =&\prod_{d}\left(\prod_{d\vert S}\prod_{T\neq\varnothing,T\subseteq S}\gcd(T)^{(-1)^{\vert T\vert+1}}\right)^{\varphi(d)} \end{aligned}

$$=\prod_{d}\left(\prod_{d\vert S}\prod_{T\neq\varnothing,T\subseteq S}\left(\sum_{k\vert T}\varphi(k)\right)^{(-1)^{\vert T\vert+1}}\right)^{\varphi(d)}$$

$$f(n)=\prod_{d\vert n}\mathrm{id}(d)^{\mu(\frac{n}{d})}$$

\begin{aligned} =&\prod_{d}\left(\prod_{d\vert S}\prod_{T\neq\varnothing,T\subseteq S}\prod_{k\vert T}f(k)^{(-1)^{\vert T\vert+1}}\right)^{\varphi(d)}\\ =&\prod_{d}\left(\prod_{k}f(k)^{\sum_{d\vert S}\sum_{T\neq\varnothing,T\subseteq S,k\vert T}(-1)^{\vert T\vert+1}}\right)^{\varphi(d)}\\ \end{aligned}

$$=\prod_{d}\left(\prod_{k}f(k)^{\sum_{d\vert S}[\exists a\in S,k\vert a]}\right)^{\varphi(d)}$$

$$\prod_{d}\left(\prod_{k}f(k)^{\lfloor\frac{m}{d}\rfloor^n-\left(\lfloor\frac{m}{d}\rfloor-\lfloor\frac{m}{\mathrm{lcm}(k,d)}\rfloor\right)^n}\right)^{\varphi(d)}$$

\begin{aligned} &\prod_{S}\mathrm{lcm}(S)^{\gcd(S)}\\ =&\prod_{S}\prod_{T\neq\varnothing,T\subseteq S}\gcd(T)^{(-1)^{\vert T\vert+1}\gcd(S)}\\ =&\prod_{S}\prod_{T\neq\varnothing,T\subseteq S}\gcd(T)^{(-1)^{\vert T\vert+1}\sum_{d\vert S}\varphi(d)}\\ =&\prod_{d}\left(\prod_{d\vert S}\prod_{T\neq\varnothing,T\subseteq S}\gcd(T)^{(-1)^{\vert T\vert+1}}\right)^{\varphi(d)}\\ =&\prod_{d}\left(\prod_{d\vert S}\prod_{T\neq\varnothing,T\subseteq S}\prod_{k\vert T}f(k)^{(-1)^{\vert T\vert+1}}\right)^{\varphi(d)}(\text{let }f(n)=\prod_{d\vert n}\mathrm{id}(d)^{\mu(\frac{n}{d})}\text{.})\\ =&\prod_{d}\left(\prod_{k}f(k)^{\sum_{d\vert S}\sum_{T\neq\varnothing,T\subseteq S,k\vert T}(-1)^{\vert T\vert+1}}\right)^{\varphi(d)}\\ =&\prod_{d}\left(\prod_{k}f(k)^{\sum_{d\vert S}[\exists a\in S,k\vert a]}\right)^{\varphi(d)}\\ =&\prod_{d}\left(\prod_{k}f(k)^{\lfloor\frac{m}{d}\rfloor^n-\left(\lfloor\frac{m}{d}\rfloor-\lfloor\frac{m}{\mathrm{lcm}(k,d)}\rfloor\right)^n}\right)^{\varphi(d)} \end{aligned}