[颓柿子] P3455 P2257

· · 个人记录

记录下怎么得到的式子。

默认 \frac ab=\lfloor \frac ab \rfloor

P3455

求 \sum\limits_{i=1}^{n}\sum\limits_{j=1}^m [(i,j)=p]。

=\sum\limits_{i=1}^{\frac n p}\sum\limits_{j=1}^{\frac m p}[(i,j)=1]

因为 \sum\limits_{d|(i,j)}\mu(d)=e((i,j))=[(i,j)=1]，所以：

=\sum\limits_{i=1}^{\frac n p}\sum\limits_{j=1}^{\frac m p}\sum\limits_{d|(i,j)} \mu(d)

这种题有个常用技巧：更换枚举顺序，即考虑外层对内层造成的贡献。我们知道 d\mid (i,j) \to d \mid i,j，所以先枚举 d，当 d\mid i,j 时答案 +\mu(d)：

=\sum\limits_{d=1}^{\frac{\min(n,m)}p}\mu(d)*\frac n{pd}\frac m{pd}

整除分块，然后预处理出 \mu 的前缀和即可。

提交记录。

P2257

求 \sum\limits_{p\in prime}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^m [(i,j)=p]。

直接套用上一题结论：

=\sum\limits_{p\in prime}\sum\limits_{d=1}^{\frac{\min(n,m)}p}\mu(d)*\frac n{pd}\frac m{pd}

为了让第一第二层联系起来，套路地设 pd=R：

=\sum\limits_{p\in prime}\sum\limits_{p\mid R}^{\min(n,m)}\mu(\frac Rp)*\frac nR\frac mR

更换枚举顺序，原式是质数向倍数贡献，那直接枚举 R 并统计其质因子的贡献即可。

=\sum\limits_{R=1}^{\min(n,m)}\sum\limits_{p\in prime,p\mid R} \mu(\frac Rp) * \frac nR * \frac mR =\sum\limits_{R=1}^{\min(n,m)}\frac nR * \frac mR\sum\limits_{p\in prime,p\mid R} \mu(\frac Rp)

整除分块，\sum\limits_{p\in prime,p\mid R} \mu(\frac Rp) 是可以预处理出来的。