HDUOJ 4947 - GCD Array

题面

对于长度为 ll 且初始全为 00 的序列 aa(下标 1l1 \sim l),有 QQ 次操作。操作分为两种:

  1. 给定 n,d,vn, d, v,对于每个满足 gcd(x,n)=d\gcd(x, n) = dxx,为 axa_x 加上 vv
  2. 给定 xx,询问 i=1xai\sum\limits_{i = 1}^{x} a_i

数据范围

1l,Q5×1041 \le l, Q \le 5 \times 10^4

1n,d,v2×1051 \le n, d, v \le 2 \times 10^5

1xl1 \le x \le l

题目链接

分析

对于操作1,如果 dnd \nmid n,则显然不可能满足 gcd(x,n)=d\gcd(x, n) = d。对于这样的情况我们忽略即可。

我们记 Δa(x)\Delta{a}(x) 代表某次进行第一种操作时位置 xx 上值的增量,有:
Δa(x)=v[gcd(x,n)=d]=v[gcd(xd,nd)=1]\begin{aligned}
\Delta{a}(x) = & v \cdot [\gcd(x, n) = d] \
= & v \cdot [\gcd(\frac{x}{d}, \frac{n}{d}) = 1]\
\end{aligned}

借助莫比乌斯函数性质,有:

Δa(x)=kgcd(xd,nd)μ(k)v=kxd,kndμ(k)v=kndkdxμ(k)v\begin{aligned}
\Delta{a}(x) = & \sum\limits_{k \mid \gcd(\frac{x}{d}, \frac{n}{d})} \mu(k) \cdot v \
= & \sum\limits_{k \mid \frac{x}{d}, k \mid \frac{n}{d}} \mu(k) \cdot v \
= & \sum\limits_{k \mid \frac{n}{d}} \sum\limits_{kd \mid x} \mu(k) \cdot v \
\end{aligned}

我们注意到,kdxμ(k)v\sum\limits_{kd \mid x} \mu(k) \cdot v 看起来十分类似莫比乌斯反演中的 F(n)F(n) 函数。既然如此,我们不妨考虑引入一个辅助数组 ff,使其满足:
a(x)=kxf(k)a(x) = \sum\limits_{k \mid x}f(k)
由此一来,我们可以通过维护 f(x)f(x) 并通过莫比乌斯反演从而求得 a(x)a(x)

根据上面推导而来的式子,我们不难发现,操作一实则是对于 nd\frac{n}{d} 的每一个因子 kk,向 f(kd)f(kd) 中增加 μ(k)v\mu(k) \cdot v


而对于操作二:
i=1xa(i)=i=1xkif(k)=k=1xxkf(k)\begin{aligned}
\sum\limits_{i = 1}^{x} a(i) = & \sum\limits_{i = 1}^{x}\sum\limits_{k \mid i}f(k) \
= & \sum\limits_{k = 1}^{x} \left\lfloor \frac{x}{k} \right\rfloor f(k)
\end{aligned}

整除分块搞一下就好了…… 由于分块需要快速求出区间和,所以可以考虑使用树状数组维护 f(x)f(x)


接下来我们简要分析一下复杂度:

对于操作1,nd\frac{n}{d} 分解质因数的复杂度 O(N)\mathcal{O}(\sqrt{N}),加上树状数组单点更新后复杂度 O(NlogN)\mathcal{O}(\sqrt{N}\log{N})

对于操作2,整除分块复杂度 O(N)\mathcal{O}(\sqrt{N}),加上树状数组区间查询后复杂度 O(NlogN)\mathcal{O}(\sqrt{N}\log{N})

妙啊!

实现

完整参考代码

%%%

This blog is under a CC BY-NC-SA 4.0 Unported License.
Link to this article: https://blog.codgician.pw/2018/11/24/hduoj-4947/