题解：P14009 数字游戏

本题可以做到 $\Theta(n\sqrt V)$ 不带 log。

首先做

\gcd

容斥，转化为对每个

v

求出

\lfloor \frac{a_i}{v} \rfloor

序列的所有区间乘积的和。

交换扫描的维度，扫描序列维，用线段树维护值域维。

于是我们要干的事情是：

n

次，每次对

\sqrt V

个区间 apply 修改，这些区间是

x

的整除分块相等的区间。

可以在线段树上并行所有修改操作，写出如下代码：

CPP

void update(int p,int l,int r,int x){
	if(x/l==x/r){
		pushtag(p,x/l);
		return;
	}
	int mid=l+r>>1;
	pushdown(p);
	update(p<<1,l,mid,x);
	update(p<<1|1,mid+1,r,x);
	pushup(p);
}

我们可以证明上面代码的复杂度是

\sqrt V

的：

对于线段树上的节点

[l,r]

，只有

\lfloor \frac{x}{l} \rfloor \ne \lfloor \frac{x}{r} \rfloor

才会递归下去。

对线段树的每层数这样的节点数，在有

V

个节点的一层，有

\Theta(\sqrt V)

个

\lfloor \frac{x}{l} \rfloor \ne \lfloor \frac{x}{r} \rfloor

的点。

总个数为

\sqrt V + \sqrt{\frac{V}{2}} + \sqrt{\frac{V}{4}} \cdots = \Theta(\sqrt V)

。

题解：P14009 数字游戏

文章操作

相关推荐

评论

题解：P14009 数字游戏