红包-解题报告

· · 题解

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

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

前置知识：莫比乌斯反演，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)

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