ShanLunjiaJian的blog

ShanLunjiaJian的blog

仰天大笑出门去,我辈就是蓬蒿人

一道可能是nowcoder上的题 题解

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

题号忘了(

题意 : 对于所有长$n$,值在$[1,m]$之间的序列$a$,求

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

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


看到一堆东西的$\mathrm{lcm}$,有两种想法 : min-max容斥,或者直接考虑每个质因子的贡献。

这里我们先尝试第二种方法,因为比较简单。考虑使用$\varphi$反演搞定那个指数上的$\gcd$(当然你用$\mu$也可以) :

$$ \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} $$

外面可以$O(m)$枚举,现在只需要考虑快速计算里面的$\mathrm{lcm}$。这是个经典问题。

把里面的东西设为$f(\lfloor\frac{m}{d}\rfloor)$,问题变为给出$m$,计算$f(m)$。

枚举质数$p$和次数$e$,考虑$p^e$的贡献。

直接统计$p^e$出现至少一次的方案数不是很简单,我们转而统计$p^e$不出现的方案数。呃这个非常简单,就是$(m-\lfloor\frac{m}{p^{e}}\rfloor)^n$嘛。那么出现的方案数就是$m^n-(m-\lfloor\frac{m}{p^{e}}\rfloor)^n$。所以$p^e$的贡献就是$(p^e)^{m^n-(m-\lfloor\frac{m}{p^{e}}\rfloor)^n}$。

吗?你发现我们算的不是次数恰好为$e$,而是至少为$e$,所以我们这里还需要对贡献进行差分(或者你对这个方案数进行差分也行,都是一样的),$p^e$的贡献实际上应该去掉那个$e$次方,变成$p^{m^n-(m-\lfloor\frac{m}{p^{e}}\rfloor)^n}$。这就做完了。复杂度是$O(n\log n\log v)$,可以预处理优化成$O(n(\log n+\log v))$,不过没啥必要。

式子完整写出来大概是这样的 :

$$ \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} $$

事实证明min-max容斥做这题比较困难,我试了半天也没有消掉那个枚举子集。

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} $$

遇到了僵局。看到$\gcd$,我们有两种办法,要么进行$\varphi$反演,要么就构造辅助函数。先试试第一种 :

$$ =\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)} $$

发现换不动啊!这个$\sum$跟$\prod$们格格不入。

那么就需要第二种了。我们构造

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

这个$f$可以$O(n\log n)$计算。然后化一下式子,就变成了

$$ \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} $$

这个指数后面那个$\sum$好像在哪里见过?干掉它。

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

最后剩下的那个指数是说,这个集合要满足每个数都被$d$整除,且某个数能被$k$整除。

进行容斥,我们分别计算 每个数都被$d$整除,没有数被$k$整除 和 每个数都被$d$整除。

容易发现后面那个是$\lfloor\frac{m}{d}\rfloor^n$。

前面那个呢,我们对每个数再容斥一次 : 用被$d$整除的减去同时被$d,k$整除的。应该是$\left(\lfloor\frac{m}{d}\rfloor-\lfloor\frac{m}{\mathrm{lcm}(k,d)}\rfloor\right)^n$。

所以答案就是 :

$$ \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)} $$

这个还是不是很好算,怎么办呢?

容易想到,满足$\mathrm{lcm}(k,d)\leq m$的$k,d$对数应该很少,而其它的次数都是$0$,不用计算。不过这个东西打表并不能很快打出来(

粗略分析一下,枚举一个$d$,枚举一个$\gcd$记为$g$(必须是$d$的因数),那么上面的式子就是$k\leq\frac{ng}{d}$,然后你发现$g$是一个调和数,$d$这里又产生一个调和数,所以这个东西是$O(n\log^2 n)$的,你也可以用这样的方法来枚举$k,d$。当然我不会真的去写这个做法。这个分析是_rqy教给我的,她说感觉实际上要比2log低,神们有兴趣可以考虑一下这个问题(

另外,当需要反演一堆$\gcd$的时候,使用$\varphi$代替$\mu$来处理$\mathrm{id}$真的很能简化推式子过程。

最后贴一遍完整过程以供欣赏 :

$$ \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} $$