Luogu4449 于神之怒加强版


Description

给定 \(n,m,k\) ,计算 \[ \sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)^k \]\(10^9+7\) 取模后的结果,其中 \(1 \leq T \le 2\times 10^3\) , \(1 \leq n,m,k \leq 5 \times 10^6\)

Solution

假设 \(n\leq m\) \[ \begin{aligned} \sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)^k &=\sum_{g=1}^{n}\sum_{i=1}^{\frac{n}{g}}\sum_{j=1}^{\frac{m}{g}} g^k*\left[(i,j)=1\right]\\ &=\sum_{g=1}^ng^k\sum_{d=1}^{\frac{n}{g}}\sum_{i=1}^{\frac{n}{dg}}\sum_{j=1}^{\frac{m}{dg}}\mu(d)\\ &=\sum_{T=1}^n\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum_{g\mid T}g^k\mu(\frac{T}{g}) \end{aligned} \]

只要预处理出 \(G(T)=\sum_{g\mid T}g^k\mu(\frac{T}{d})\) 即可,\(O(n\log n)\) 会超时 。注意到这是两个积性函数的狄利克雷卷积,所以它仍然是一个积性函数,又由于 \(\mu\) 的特殊性有: \[ \begin{aligned} G(T)&=\prod G(P_i^{x_i})\\ &=\prod (P_i^{x_i-1})^k\mu(P_i)+(P_i^{x_i})^k\mu(1)\\ &=\prod (P_i^{x_i-1})^k(P_i^k-1) \end{aligned} \]

所以有:

\[ \begin{aligned} G(i*P_j)=\left\{ \begin{array}{lrr} P_j^k-1 & i=1\\ G(i)*P_j^k & P_j\mid i\\ G(i)*G(P_j) & P_j\nmid i\\ \end{array} \right. \end{aligned} \]


文章作者: ffacs
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 ffacs !
  目录