2025杭电多校第十场 Cut Check Bit、Multiple and Factor 个人题解

Multiple and Factor

根号分治 #数学

题目

思路


本题采用根号分治的思想，令\(B=\sqrt{ n }\)，将下标分为\(1\leq i\leq B\)与\(BB\)：

• 可知此时的\(x\)的倍数个数不会超过\(B\)个，因此可以暴力解决
  
• 枚举\(x\)的所有倍数\(tx\)，\(a[tx]+=k\)
  
• 时间复杂度\(o(B)\)
  

</ul>操作二：令\(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\)对答案的贡献即\(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[B]\)，用于直接储存操作三小数询问的答案
    
  • 进行操作一时：(令\(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[B]\)，\(d\)表示数字\(i\)的因数个数，求\(d\ |\ t\)的个数即\(d[t]=d\left[ \frac{x}{i} \right]\)
      
    • 因此\(addmul+=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\)
    
  
  
• 时间复杂度\(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}^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 (x  x >> k;            for (int i = 1;i * i > x;            int ans = 0;            if (x