2025杭电多校第十场Cut Check Bit、Multiple and Factor题解如何获取？

Multiple and Factor 根号分治 #数学 题目 思路 本题采用根号分治的思想，令\(B=\sqrt{ n }\)，将下标分为\(1\leq i\leq B\)与\(B<i\leq n\)两类数进行维护 数组\(a[N]\)用于储存初始权值 操作一：令\(x\)的所有倍数位置\(+k\) 若\(x\leq B\)： 创建数组\(add[B]\)，作为小数倍数和的加法懒标记 直接 \(add[x]+=k\)即可 时间复杂度\(o(1)\) 若\(x>B\)： 可知此时的\(x\)的倍数个数不会超过\(B\)个，因此可以暴力解决 枚举\(x\)的所有倍数\(tx\)，\(a[tx]+=k\) 时间复杂度\(o(B)\) 操作二：令\(x\)的所有因数位置\(+k\) 直接枚举\(x\)的所有因数\(d\) \(a[d]+=k\ [\ d\ |\ x\ ]\) 时间复杂度\(o(\sqrt{ n })\) 操作三：查询\(x\)的所有倍数位置的权值和 若\(x>B\)： 先暴力枚举\(x\)的所有倍数\(tx\)，\(ans+=a[tx]\) 接下来需要处理\(1\leq i\leq B\)部分的加法懒标记： 设集合\(S_{i}=\{ j\ |\ j=t\times i\ ,\ j\leq n\ ,\ t\geq 1 \}\)，表示所有小于\(n\)的\(i\)的倍数集合 可知\(S_{i}\cap S_{x}=S_{lcm(x,i)}\) \(add[i]\)对答案的贡献即\(add[i]\times S_{lcm(x,i)}.size\) 而\(S_{j}.size=\left\lfloor \frac{n}{j} \right\rfloor\) 因此\(ans+=add[i]\times \left\lfloor \frac{n}{lcm(x,i)} \right\rfloor\) 时间复杂度\(o(B+B\log n)\)，\(\log n\)来自\(lcm(x,i)\) 若\(x\leq B\)： 这些数不好用懒标记维护，所以直接每次修改都暴力维护 创建数组\(addmul[B]\)，用于直接储存操作三小数询问的答案 进行操作一时：(令\(x\)的所有倍数位置\(+k\)) 考虑直接更新\(1\leq i\leq B\)的\(addmul[i]\) 同样考虑\(S_{i}\)与\(S_{x}\)两个集合，可得\(addmul[i]+=k\times\left\lfloor \frac{n}{lcm(x,i)} \right\rfloor\) 时间复杂度\(o(B\log n)\) 进行操作二时：(令\(x\)的所有因数位置\(+k\)) 考虑直接更新\(1\leq i\leq B\)的\(addmul[i]\) 首先\(i\)必须是\(x\)的因数才会被更新到，即\(i\ |\ x\) 设\(t\times i=x\)，若\(d\ |\ t\)，则\((d\times i)\ |\ x\)，因此\(d\)的数量即为又是\(i\)的倍数又是\(x\)的因数的个数 创建数组\(d[B]\)，\(d[i]\)表示数字\(i\)的因数个数，求\(d\ |\ t\)的个数即\(d[t]=d\left[ \frac{x}{i} \right]\) 因此\(addmul[i]+=k\times d\left[ \frac{x}{i} \right]\) 时间复杂度\(o(B)\) 操作四：查询\(x\)的所有因数位置的权值和 先暴力枚举\(x\)的所有因数\(d\)，\(ans+=a[d]\) 接下来处理小数部分的加法懒标记： 对于\(1\leq i\leq B\)且\(i\ |\ x\)，同样也是考虑“又是\(i\)的倍数又是\(x\)的因数的个数” 因此\(ans+=d\left[ \frac{x}{i} \right]\times add[i]\) 时间复杂度\(o(\sqrt{ n }+B)\) 对于数组\(d[B]\)，可以通过类似欧拉筛的方法预处理： 枚举\(1\leq i\leq n\)，对于每个\(i\)再枚举\(k\times i\leq n\)，\(d[k\times i]++\) 对于每个确定的\(i\)，将会枚举\(\left\lfloor \frac{n}{i} \right\rfloor\)个\(k\)，因此总枚举次数为\(\sum_{i=1}^n\left\lfloor \frac{n}{i} \right\rfloor\) 复杂度为\(o\left( \sum_{i=1