题解：P17238 『STA - R10』Petal Dance

· · 题解

暴力推式子，还有个大坑。

\sum_{k=1}^{n}\sum_{i=1}^{n}\sum_{j=1}^{n} \gcd(ij,k) = \newline \sum_{k=1}^{n}\sum_{d \mid k}d \times \sum_{i=1}^{n}\sum_{j=1}^{n}[d \mid ij][\gcd(\frac{ij}{d},\frac{k}{d}) = 1] \newline =\sum_{k=1}^{n}\sum_{d \mid k}d \times \sum_{Td \mid k}\mu(T)\sum_{i=1}^{n}\sum_{j=1}^{n}[dT \mid ij]

注意到有 dT 这坨东西出现了两次考虑枚举它，并使用万能的交换求和顺序，再考虑到内层的 \sum_{i=1}^{n}\sum_{j=1}^{n}[dT \mid ij] 也只与这坨有关，考虑令 f(d) = \sum_{i=1}^{n}\sum_{j=1}^{n}[d \mid ij]。于是带进去就美观些了吗。

\sum_{k=1}^{n}\sum_{d \mid k}d \times \sum_{Td \mid k}\mu(T)\sum_{i=1}^{n}\sum_{j=1}^{n}[dT \mid ij] = \newline \sum_{k=1}\sum_{d \mid k}f(d)\sum_{T \mid d}\mu(T) \times \frac{d}{T}

注意到后面那一坨等价于 \sum_{T \mid d}\mu(T) \times \operatorname{id}_{\frac{T}{d}}，使用一点点魔法狄利克雷卷积知识，[(\operatorname{id} * \mu)(n) = \sum_{d|n} \operatorname{id}(d) \mu(\frac{n}{d})] = \phi(n)，相信大家做这道题这些已经不成问题了。所以原式就真正变的美观了。

\sum_{k=1}^{n}\sum_{d \mid k}f(d) \times \phi(d)

欧拉筛即可求出后者，对于前面这一坨，需要特殊处理，但千万不要强行把 f 打开然后用莫比乌斯反演硬推，多半会和我一样推出来 f(T)=\sum_{d \mid T}\mu(d) \sum_{k \mid \frac{T}{d}} \lfloor\frac{nk}{T}\rfloor \times \lfloor \frac{n}{dk} \rfloor，死活化简不出来，至少我是不行，或许有大神可以，但那也就不用看这篇题解了。

考虑另一种方法。不用莫比乌斯反演，而是把它表示成别的函数，剥洋葱一样解决之。也就是说如果 k \mid ij，就说明 \frac{k}{\gcd(i,k)} \mid j，就可以进一步变形。

\sum_{i=1}\sum_{j=1}[k \mid ij]=\sum_{i=1}^{n}\lfloor\frac{n\gcd(i,k)}{k} \rfloor =\newline \sum_{ij=k}\lfloor\frac{n}{j}\rfloor \sum_{T=1}^{\lfloor\frac{n}{i}\rfloor}[\gcd(T,j)=1]

经过血的教训（比赛时卡了老久），不能把它强行展开，而是二度替换，令 g(i,j)=\sum_{T=1}^{\lfloor\frac{n}{i}\rfloor}[\gcd(T,j)=1]，然后考虑怎么算这玩意

。若 q 为质数或 1 显然简单，由于合法的 (i,j) 数量是调和级数，即 \mathcal{O}(n\log{n})，所以我们需要 \mathcal{O}(1) 递推算出每一对。

考虑 j 的最小质因子 p，若有 p^2 \mid j，则有 g(i,j) = g(i,\frac{j}{p}) ，因为内层等价于是互质，所以只要不把这个质因子除干净了，互质与否不会有改变。

若没有这条件，即 x^2 \nmid j，那么 g(i,j) = g(i,\frac{j}{p}) - g(ip,\frac{j}{p}) ，证明考虑原式意义，g(i,\frac{j}{p}) 就是统计的是与 \frac{j}{p} 互素的 T，其中包含了 p \mid T 的部分，而 j 比 \frac{j}{p} 多了一个质因子 p，所以要减去这一部分把 T' = pT 代入后，恰好就是 g(ip,\frac{j}{p})。遂可以推了，n 有 5 \times 10^6，需要注意常数。

经过略略卡常，用了个火车头，从平板电视哈希表硬存 g(i,j) 到 vector 到静态数组，从取模到加减与短路到巴雷特约减，就轻松无压力地过了。洛谷评测机确实比本机好。本地 4.7 秒，，洛谷直接过了。对了 g(1,i) 可以直接算，不用存，再节省点。

代码\color{black} 。