题解 P4449 【于神之怒加强版】

[P4449 于神之怒加强版](https://www.luogu.com.cn/problem/P4449) $$ ans=\sum_{i=1}^n\sum_{j=1}^mgcd(i,j)^k $$ $$ \begin{aligned} ans & = \sum_{i=1}^n\sum_{j=1}^mgcd(i,j)^k \\ & =\sum_{i=1}^{n}\sum_{j=1}^m\sum_{t=1}^{min(i,j)}t^k\cdot[gcd(i,j)=t] \\ & =\sum_{t=1}^{n}t^k\sum_{i=1}^{\left\lfloor\dfrac{n}{t}\right\rfloor}\sum_{j=1}^{\left\lfloor\dfrac{m}{t}\right\rfloor}[gcd(i,j)=1] \\ & =\sum_{t=1}^{n}t^k\sum_{i=1}^{\left\lfloor\dfrac{n}{t}\right\rfloor}\sum_{j=1}^{\left\lfloor\dfrac{m}{t}\right\rfloor}\sum_{d|gcd(i,j)}\mu(d) \\ & =\sum_{t=1}^{n}t^k\sum_{d=1}^{\left\lfloor\dfrac{n}{t}\right\rfloor}\mu(d)\cdot\left\lfloor\dfrac{n}{dt}\right\rfloor\cdot\left\lfloor\dfrac{m}{dt}\right\rfloor \\ & =\sum_{D=1}^n\left\lfloor\dfrac{n}{D}\right\rfloor\cdot\left\lfloor\dfrac{m}{D}\right\rfloor\sum_{t|D}t^k\mu(\frac{D}{t}) \end{aligned} $$ 前面的就是数论分块 后面的…… 设为 $$ f(x)=\sum_{t|x}t^k\mu(\frac{x}{t}) $$ 我们来套路性的分析这个可以筛出来的函数 > x 属于质数 $$ f(x)=x^k-1 $$ > x是1 $$ f(x)=1 $$ > $x=i * prime[j]$ > > > $i\;mod\;prime[j] \neq 0$ > > $$ > f(x) = f(i) * f(prime[j]) > $$ > > > $i\;mod\;prime[j] = 0$ > > $$ > f(x)=f(i)*prime[j]^k > $$ > > 所以我们现在可以愉快地码代码了