2025杭电多校第十场 Cut Check Bit、Multiple and Factor 个人题解
Multiple and Factor根号分治 #数学
题目
思路
本题采用根号分治的思想，令\(B=\sqrt{ n }\)，将下标分为\(1\leq i\leq B\)与\(BB\)：
[*]可知此时的\(x\)的倍数个数不会超过\(B\)个，因此可以暴力解决
[*]枚举\(x\)的所有倍数\(tx\)，\(a+=k\)
[*]时间复杂度\(o(B)\)
</ul>操作二：令\(x\)的所有因数位置\(+k\)
[*]直接枚举\(x\)的所有因数\(d\)
[*]\(a+=k\ [\ d\ |\ x\ ]\)
[*]时间复杂度\(o(\sqrt{ n })\)
操作三：查询\(x\)的所有倍数位置的权值和
[*]若\(x>B\)：
[*]先暴力枚举\(x\)的所有倍数\(tx\)，\(ans+=a\)
[*]接下来需要处理\(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\)对答案的贡献即\(add\times S_{lcm(x,i)}.size\)
[*]而\(S_{j}.size=\left\lfloor\frac{n}{j}\right\rfloor\)
[*]因此\(ans+=add\times \left\lfloor\frac{n}{lcm(x,i)}\right\rfloor\)
[*]时间复杂度\(o(B+B\log n)\)，\(\log n\)来自\(lcm(x,i)\)
[*]若\(x\leq B\)：
[*]这些数不好用懒标记维护，所以直接每次修改都暴力维护
[*]创建数组\(addmul\)，用于直接储存操作三小数询问的答案
[*]进行操作一时：(令\(x\)的所有倍数位置\(+k\))
[*]考虑直接更新\(1\leq i\leq B\)的\(addmul\)
[*]同样考虑\(S_{i}\)与\(S_{x}\)两个集合，可得\(addmul+=k\times\left\lfloor\frac{n}{lcm(x,i)}\right\rfloor\)
[*]时间复杂度\(o(B\log n)\)
[*]进行操作二时：(令\(x\)的所有因数位置\(+k\))
[*]考虑直接更新\(1\leq i\leq B\)的\(addmul\)
[*]首先\(i\)必须是\(x\)的因数才会被更新到，即\(i\ |\ x\)
[*]设\(t\times i=x\)，若\(d\ |\ t\)，则\((d\times i)\ |\ x\)，因此\(d\)的数量即为又是\(i\)的倍数又是\(x\)的因数的个数
[*]创建数组\(d\)，\(d\)表示数字\(i\)的因数个数，求\(d\ |\ t\)的个数即\(d=d\left[ \frac{x}{i} \right]\)
[*]因此\(addmul+=k\times d\left[ \frac{x}{i} \right]\)
[*]时间复杂度\(o(B)\)
操作四：查询\(x\)的所有因数位置的权值和
[*]先暴力枚举\(x\)的所有因数\(d\)，\(ans+=a\)
[*]接下来处理小数部分的加法懒标记：
[*]对于\(1\leq i\leq B\)且\(i\ |\ x\)，同样也是考虑“又是\(i\)的倍数又是\(x\)的因数的个数”
[*]因此\(ans+=d\left[ \frac{x}{i} \right]\times add\)
[*]时间复杂度\(o(\sqrt{ n }+B)\)
对于数组\(d\)，可以通过类似欧拉筛的方法预处理：
[*]枚举\(1\leq i\leq n\)，对于每个\(i\)再枚举\(k\times i\leq n\)，\(d++\)
[*]对于每个确定的\(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}^n\left\lfloor\frac{n}{i}\right\rfloor \right)=o\left( \sum_{i=1}^n \frac{n}{i} \right)=o\left( n·\sum_{i=1}^n \frac{1}{i} \right)\)，由\(\sum_{n=1}^x \frac{1}{n}\leq 1+\ln x\)可知，复杂度为\(o(n\log n)\)（文末证明）
至此，由于\(B=\sqrt{ n }\)，总复杂度来到\(o(n\log n+m·\sqrt{ n }·\log n)\)，但由于\(\sqrt{ n }·\log n\)的原因，会\(TLE\)
因此考虑预处理\(gcd(a,b)\)从而将\(\log n\)消去：
<ul>因为调用时\(lcm(x,i)\)中\(1\leq i\leq B\)，而对于\(x>B\)，辗转相除一次之后也将变为\(x\leq B\) ，因此仅预处理所有\(1\leq a,b\leq B\)的\(gcd(a,b)\)
枚举所有\(1\leq i x >> k; if (xx >> k; for (int i = 1;i * i > x; int ans = 0; if (x
页:
[1]