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

· · 题解

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

所以我们现在可以愉快地码代码了