题解：P14009 数字游戏

Rainbow_qwq · 2025-09-14 21:48:17 · 题解

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

首先做 \gcd 容斥，转化为对每个 v 求出 \lfloor \frac{a_i}{v} \rfloor 序列的所有区间乘积的和。

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

于是我们要干的事情是：n 次，每次对 \sqrt V 个区间 apply 修改，这些区间是 x 的整除分块相等的区间。

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

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)。