整除分块

WZH2026-05-262026-05-26

数论

~~我为什么会写这个？~~

整除分块

如果你想在 $O(\sqrt{n})$ 时间内求解如下式子：

\sum_{i=1}^n f(i)g(\lfloor\frac{n}{i})\rfloor

满足 $O(1)$ 求取 $f$ 函数的前缀和， $O(1)$ 求取 $g$ 函数单点值。

这时候就需要用到整除分块了。

看引理：

引理 1 ：

$\lfloor\frac{n}{i}\rfloor$ 的不同取值个数为 $O(\sqrt{n})$ 个。

引理 2 ：

对于整数 $k$ ，对于所有的 $i$ 满足 $\lfloor\frac{n}{i}\rfloor=k$ ， $i$ 的取值连续。

那么我们可以枚举这 $O(\sqrt{n})$ 个取值，从而在 $O(\sqrt{n})$ 内求解。

但是我们还有一个问题：假设当前枚举的取值为 $\lfloor\frac{n}{l}\rfloor$ ，所有取到这一个取值的点的左端点为 $l$ ，如何求解右端点？

引理 3 ：

对于 $l$ ，有所有满足 $\lfloor\frac{n}{i}\rfloor=\lfloor\frac{n}{l}\rfloor$ 的 $i$ 的最大值为 $\lfloor\frac{n}{\lfloor\frac{n}{l}\rfloor}\rfloor$ 。

证明：

看引理：

所以显然有 $i=\lfloor\frac{n}{\lfloor\frac{n}{l}\rfloor}\rfloor$ 满足 $\lfloor\frac{n}{i}\rfloor=\lfloor\frac{n}{l}\rfloor$ 。

设 $r=\lfloor\frac{n}{\lfloor\frac{n}{l}\rfloor}\rfloor$ ，则显然有 $l \le r$ 。

并且，对于任意满足条件的 $i$ ，都有 $\lfloor\frac{n}{i}\rfloor=\lfloor\frac{n}{r}\rfloor$ 。

所以有 $\lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor=\lfloor\frac{n}{\lfloor\frac{n}{r}\rfloor}\rfloor$ 。

同时又因为 $\lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor \ge i$ ，所以 $r\ge i$ ，所以得证。

于是我们就可以在 $O(\sqrt{n})$ 的时间内解决这个问题了。

伪代码：

int res=0;
for(int l=1,r;l<=n;l=r+1){
    r=n/(n/l);
    res+=F_sum(l,r)*g(n/l);
}

P2261 [CQOI2007] 余数求和

题目： [CQOI2007] 余数求和。

题目内容：

给定 $n,k \le 10^9$ ，求：
$\sum_{i=1}^n k \bmod i$

引理 4 （余数定义 & 小学知识）：
$n\bmod i=n-i\lfloor\frac{n}{i}\rfloor$

这样就是整除分块经典形式了。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=100010;
#define ll long long
ll n,k,ans;
int main(){
    cin>>n>>k;
    ans=n*k;
    int l=1,r;
    for(;l<=n;l=r+1){
        if(k/l!=0)r=min(n,k/(k/l));
        else r=n;
        ans-=(k/l)*(l+r)*(r-l+1)/2;
    }
    cout<<ans;
    return 0;
}

P2260 [清华集训 2012] 模积和

题目： [清华集训 2012] 模积和。

题目描述：

给定 $n,m \le 10^9$ ，求：
$\sum_{i=1}^n\sum_{j=1,i\ne j}^m (n \bmod i)(m\bmod j)$

首先容斥掉 $i\ne j$ 的条件得到 $\displaystyle\sum_{i=1}^n\sum_{j=1}^m (n \bmod i)(m\bmod j)-\displaystyle\sum_{i \le n,i\le m} (n\bmod i)(m\bmod i)$ 。

对于前面的式子，由于 $n\bmod i$ 和 $m\bmod j$ 无关，可以拆开。

对于后面的式子，可以使用引理 4 转化为：

\sum_{i=1}^n \lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{i}\rfloor

这个的处理和原版本类似：

1	r=min(n/(n/l),m/(m/l));

这样就行了，其他的一样。

代码：

#include <bits/stdc++.h>
using namespace std;
const int P=19940417;
int n,m;
const int inv2=9970209,inv6=3323403;
int S1(int n){return 1ll*n*(n+1)%P*inv2%P;}
int S2(int n){return 1ll*n*(n+1)%P*(2*n%P+1)%P*inv6%P;}
int calc(int n,int k){
    int ans=0;
    for(int l=1,r;l<=k;l=r+1){
        r=min(k,n/(n/l));
        (ans+=1ll*(S1(r)-S1(l-1)+P)%P*(n/l)%P)%=P;
    }
    return ans;
}
int Calc(int n,int m){
    int ans=0;
    for(int l=1,r;l<=min(n,m);l=r+1){
        r=min(n/(n/l),m/(m/l));
        (ans+=1ll*(S2(r)-S2(l-1)+P)%P*(n/l)%P*(m/l)%P)%=P;
    }
    return ans;
}
int main(){
    cin>>n>>m;
    int t1=(1ll*n*n%P+P-calc(n,n))%P;
    int t2=(1ll*m*m%P+P-calc(m,m))%P;
    int t3=Calc(n,m);
    int t4=1ll*n*m%P*min(n,m)%P;
    int t5=1ll*n*calc(m,min(n,m))%P;
    int t6=1ll*m*calc(n,min(n,m))%P;
    int T1=(1ll*t1*t2%P)%P;
    int T2=(P-t3+P-t4)%P;
    int T3=(t5+t6)%P;
    cout<<((T1+T2)%P+T3)%P; 
    return 0;
}