自动搬运

查看原文

来自洛谷，原作者为

	LHF qwq

搬运于2025-08-24 22:29:07，当前版本为作者最后更新于2021-02-03 15:22:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

看到很多人都用了计算每个质数的贡献来做出这道题的……

先讲一下出题人原来的做法

前置知识：莫比乌斯反演，min-max容斥，二项式定理。

Step1.

好了，我们设集合$T$(与上文无关)的大小为$n$，即$n=|T|$，并且$lcm(T)=lcm(T_1,T_2...T_n),gcd(T)=gcd(T_1,T_2...T_n)$

则有$\displaystyle lcm(T)=\prod_{S\subsetneq T}gcd(S)^{(-1)^{|S|}}$

证明：考虑min-max容斥。

我们可以把每一个质数分开考虑，显然，$lcm(p^a,p^b)=p^{\max(a,b)},gcd(p^a,p^b)=p^{\min(a,b)}$（$p$是个质数），多个数同理。然后直接套用min_max容斥的结论即可，记得把加法改成乘法，减法变成的除法。

Q：为什么可以这么做呢？

A：这显然，因为同底数幂相乘，底数不变，指数相加。

Step2.

设

$$F(n,K)=\prod_{i_1=1}^n\prod_{i_2=1}^n...\prod_{i_k=1}^n\gcd(i_1,i_2...i_k) $$$$=\prod_{k=1}^nk^{\sum_{i_1=1}^{n}\sum_{i_2=1}^{n}...\sum_{i_K=1}^{n}[\gcd(i_1,i_2...i_K)=k]} $$

（注意：区分大小写）

考虑指数上面那一坨东西

$$\sum_{i_1=1}^{n}\sum_{i_2=1}^{n}...\sum_{i_K=1}^{n}[\gcd(i_1,i_2...i_K)=k]=\sum_{d=1}^{\lfloor\frac{n}{k}\rfloor}\lfloor\frac{n}{kd}\rfloor^K\mu(d) $$

再带回去得到

$$F(n,k)=\prod_{k=1}^n\prod_{d=1}^{\lfloor\frac{n}{k}\rfloor}k^{\lfloor\frac{n}{kd}\rfloor^K\mu(d)} $$

设$T=kd$，枚举$T$得到：

$$F(n,k)=\prod_{T=1}^n(\prod_{d|T}d^{\mu(\frac{T}{d})})^{\lfloor\frac{n}{T}\rfloor^K} $$

Step3.

现在看到题目要求求的这个东西，带入Step1、Step2求出的公式，我们发现题目就是求：

$$\prod_{i=1}^K F(n,i)^{(-1)^{i+1}\times C_K^i\times n^{K-i}} $$

顺便说一句，$\displaystyle F(n,1)=\prod_{i=1}^ni$

我们分析一下

$$F(n,k)=\prod_{T=1}^n(\prod_{d|T}d^{\mu(\frac{T}{d})})^{\lfloor\frac{n}{T}\rfloor^K} $$

那么$F(n,K)^a=\prod_{T=1}^n(\prod_{d|T}d^{\mu(\frac{T}{d})})^{a\times\lfloor\frac{n}{T}\rfloor^K}$

其实我们可以发现$F(n,a)$和$F(n,b)$只有后面那一坨的指数不同，考虑幂的乘方，底数不变，指数相乘。

把题目中的那一坨式子带入得到：

$$ans=\prod_{T=1}^n(\prod_{d|T}d^{\mu(\frac{T}{d})})^? $$

好了，我们现在想一想式子中的$?$是什么。

显然，$?=C_K^1\times n^{K-1}\times\lfloor\frac{n}{T}\rfloor-C_K^2\times n^{K-2}\lfloor\frac{n}{T}\rfloor^2+...=\sum_{i=1}^K(-1)^{i+1}C_{K}^i\times n^{K-i}\times\lfloor\frac{n}{T}\rfloor^i$

运用二项式定理，可得$?=n^K-(n-\lfloor\frac{n}{T}\rfloor)^K$

好了，终于搞好了……好累啊。

带入即可。

$$ans=\prod_{T=1}^n(\prod_{d|T}d^{\mu(\frac{T}{d})})^{n^K-(n-\frac{n}{T})^K} $$

然后预处理一下$\displaystyle\prod_{d|T}d^{\mu(\frac{T}{d})}$就可以啦！

哦，对了，指数上的$n^K$和另一个东西在$K$很大的时候记得优化哦，根据费马小定理，我们要求求出$n^K\mod998244352$，然后根据拓展欧拉定理搞一搞就可以把时间复杂度降下来了。

时间复杂度：$O(T\sqrt n\log k+n\log n)$

啥？你还不会做？赶紧去重新学习莫比乌斯反演吧。

其实题目还可以出得更难一点的，但是良心的出题人认为算了，就这样吧……

下面给出出题人设置每个数据点的意图

数据点	设置意图
0	会暴力
1	会普通的莫比乌斯反演，但不会容斥
2	同上，不过容斥学得稍微好点
3	我也不知道，不过也许……
4	想到了容斥但是不会快速处理$F(n,k)$的
5	能快速计算但是时间复杂度依赖$K$的
6	单次询问时间复杂度为$O(n\log k)$的
7	单词询问时间复杂度为$O(\sqrt n\log k)$的
8	能运用拓展欧拉定理优化$K$的
9	恭喜，您已做出此题。

彩蛋

为了防止被吊打，出题人特意准备了一个彩蛋。

这是蔡鸟Bird提出的做法，也就是考虑每一个质因数的贡献，同样也是大多数人选择的做法。

跟上面的做法差不多。

其实考虑$F(T)=\prod_{d|T}d^{\mu(T/d)}$，若T是某一个质数$p$的若干次方，那么$F(T)=p$，否则$F(T)=1$，其实也是在计算质数的贡献。

这样子可以做到$O(n+T\sqrt n\log k)$

啥？你还能够吊打标算？那我认输了……