题解：SP4195 MSE08H - GCD Determinant

· · 题解

模拟赛出了这题的加强版。

因为 \sum\limits_{d\mid \gcd(x_i,x_j)} \varphi(d)=\gcd(x_i,x_j)，所以考虑根据前一个式子转化矩阵。这个矩阵要有整除关系，并且两个元素之积是欧拉函数，不难构造一个矩阵 A_{i,j}=\begin{cases} \ \sqrt{\varphi(x_i)},(x_i\mid x_j) \\ 0, \operatorname{otherwise} \end{cases}。

然后发现 D=\sum\limits _{k=1}^n A_{k,i}A_{k,j}=AA^T。所以 |D|=|A||A^T|=|A|^2。你发现 A 是下三角矩阵，所以答案变为：(\prod\limits_{i=1}^n \sqrt{\varphi(x_i)})^2=\prod\limits_{i=1}^n \varphi(x_i)。

但模拟赛的是加强版。我们记这个集合的 \operatorname{lcm} 为 n，那道题给你 n 的唯一分解，即 n=\prod\limits_{i=1}^t p_i^{q_i},p_i\le7368790,q_i\le 10^9,t\le 5\times 10^5。

这怎么做？

因为 \varphi(x)=x\prod\limits_{i=1}^t\frac{p_i-1}{p_i}=\prod\limits_{i=1}^t(p_i-1)\times p_i^{q_i-1},x=p_1^{q_1}p_2^{q_2}\cdots p_t^{q_t}，所以每个 p_i 对他的一个倍数 d 的贡献就是 (p_i-1)p_i^{k-1},k=\max\limits_{p_i^j\mid d} j。这样的 d 的个数是 \prod\limits_{j\ne i}(q_j+1)。所以答案就是：\prod\limits_{i=1}^t (\prod\limits_{j=1}^{q_i}(p_i-1)p_i^{j-1})^{\frac{s}{q_i+1}}=\prod\limits_{i=1}^t ((p_i-1)^{q_i} p_i^{\frac{(q_i-1)q_i}{2}})^{\frac{s}{q_i+1}}，其中 s=\prod\limits_{j=1}^n (q_j+1)。

复杂度做到 O(t\log P+\max p)。