数论分块()

数论分块

数论分块

也叫整除分块

是用于快速处理类似于

式子的一种方法

复杂度：\(O(\sqrt{n})\)

思想阐述：以向下取整为例

对于\(\lfloor \frac{n}{i}\rfloor\)，来说，它的值是呈块状递减分布的，至多有\(2\sqrt{n}\)个块

这些块的分布规律是：

对于一个块内的一个点\(l\)，我们可以得到块的右端点为\(\lfloor \frac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor\)

写成代码就是

int get(int l){return n/(n/l);}

非常的\(so\)  \(easy\)

那么我们要求的 \(\sum_{i=1}^n \lfloor \frac{n}{i} \rfloor\)

也就迎刃而解了

for(int i=1;i<=n;i++){
   int r=get(i);
   ans+=(n/i)*(r-i+1);
   i=r;
}

还有一个性质：

来一道例题吧：

余数之和（CQOI2007）

题意简述：给定\(n,k\)求：

注意到\(k \bmod i=k-\lfloor \frac{k}{i} \rfloor \times i\)

所以

由于数论分块，我们设\(\sum_{i=1}^n \lfloor \frac{k}{i} \rfloor\)分成了\(m\)个块，各个块的左右端点记作\(L_i,R_i(i\in [1,m])\)

则原式子可化为：

综上所述，答案即为：

\(Code:\)

cin>>n>>k;
ans=n*k;
for(int x=1,gx;x<=n;x=gx+1){
    gx=k/x?min(k/(k/x),n):n;
    ans-=(k/x)*(x+gx)*(gx-x+1)/2;
}
cout<<ans;
————————

数论分块

数论分块

也叫整除分块

是用于快速处理类似于

式子的一种方法

复杂度：\(O(\sqrt{n})\)

思想阐述：以向下取整为例

对于\(\lfloor \frac{n}{i}\rfloor\)，来说，它的值是呈块状递减分布的，至多有\(2\sqrt{n}\)个块

这些块的分布规律是：

对于一个块内的一个点\(l\)，我们可以得到块的右端点为\(\lfloor \frac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor\)

写成代码就是

int get(int l){return n/(n/l);}

非常的\(so\)  \(easy\)

那么我们要求的 \(\sum_{i=1}^n \lfloor \frac{n}{i} \rfloor\)

也就迎刃而解了

for(int i=1;i<=n;i++){
   int r=get(i);
   ans+=(n/i)*(r-i+1);
   i=r;
}

还有一个性质：

来一道例题吧：

余数之和（CQOI2007）

题意简述：给定\(n,k\)求：

注意到\(k \bmod i=k-\lfloor \frac{k}{i} \rfloor \times i\)

所以

由于数论分块，我们设\(\sum_{i=1}^n \lfloor \frac{k}{i} \rfloor\)分成了\(m\)个块，各个块的左右端点记作\(L_i,R_i(i\in [1,m])\)

则原式子可化为：

综上所述，答案即为：

\(Code:\)

cin>>n>>k;
ans=n*k;
for(int x=1,gx;x<=n;x=gx+1){
    gx=k/x?min(k/(k/x),n):n;
    ans-=(k/x)*(x+gx)*(gx-x+1)/2;
}
cout<<ans;