数论求和

数论求和把按整数逐项枚举的问题，转化为对整除商、数论函数前缀和与卷积系数的批量计算。

1 从卷积变形到高效计算

经过莫比乌斯反演或狄利克雷卷积后，许多题目会化为

$$\sum_{d=1}^{N} f(d) \left\lfloor\frac nd\right\rfloor \left\lfloor\frac md\right\rfloor$$

或

$$\sum_{d=1}^{N} f(d)\, S\left(\left\lfloor\frac nd\right\rfloor\right) S\left(\left\lfloor\frac md\right\rfloor\right).$$

本章主线：数论函数前缀和 → 整除分块 → 二维整除分块 → 常见 $\gcd$ 类求和 → 带权求和 → 杜教筛。

卷积负责找到正确的权函数，整除分块负责减少枚举次数，杜教筛则负责在预处理范围不足时计算数论函数前缀和。

---

2 整除分块

2.1 相同整除商形成区间

固定正整数 $n$，函数 $\lfloor n/i\rfloor$ 的取值并不会在每个 $i$ 处都改变。

若当前左端点为 $l$，令

$$v=\left\lfloor\frac nl\right\rfloor,$$

那么所有满足 $\lfloor n/i\rfloor=v$ 的 $i$ 构成连续区间

$$\left[l,\left\lfloor\frac nv\right\rfloor\right].$$

因此右端点可以直接取为

$$r=\left\lfloor\frac n{\lfloor n/l\rfloor}\right\rfloor.$$

$\lfloor n/i\rfloor$ 只有 $O(\sqrt n)$ 种不同取值，所以整除分块可以在 $O(\sqrt n)$ 个区间内完成遍历。

2.2 一维分块

若要求

$$\sum_{i=1}^{n} f(i)\left\lfloor\frac ni\right\rfloor,$$

并已知前缀和 $F(x)=\displaystyle\sum_{i=1}^{x}f(i)$，那么在区间 $[l,r]$ 上整除商相同，可以写成

$$\sum_{i=l}^{r}f(i)\left\lfloor\frac ni\right\rfloor = \bigl(F(r)-F(l-1)\bigr)\left\lfloor\frac nl\right\rfloor.$$

▶

一维整除分块

ll pre[maxn];

ll calc( ll n ) {
    ll res = 0;

    for( ll l = 1, r; l <= n; l = r + 1 ) {
        ll v = n / l;
        r = n / v;

        res += ( pre[r] - pre[l - 1] ) * v;
    }
    return res;
}

2.3 除数求和

经典例子是

$$F(n)=\sum_{i=1}^{n}\left\lfloor\frac ni\right\rfloor.$$

它同时等于 $1$ 到 $n$ 的因数个数前缀和：

$$F(n)=\sum_{i=1}^{n}\tau(i).$$

因为每个 $i$ 对 $\lfloor n/i\rfloor$ 的贡献，表示 $i$ 的倍数在 $1$ 到 $n$ 中出现了多少次。

▶

除数求和

ll F( ll n ) {
    ll res = 0;

    for( ll l = 1, r; l <= n; l = r + 1 ) {
        ll v = n / l;
        r = n / v;

        res += v * ( r - l + 1 );
    }
    return res;
}

---

3 二维整除分块

3.1 同时固定两个整除商

若式子中同时出现 $\lfloor n/d\rfloor$ 与 $\lfloor m/d\rfloor$，需要让两者在同一个区间内都保持不变。

设

$$v_n=\left\lfloor\frac nl\right\rfloor,\qquad v_m=\left\lfloor\frac ml\right\rfloor,$$

那么右端点为

$$r=\min\left( \left\lfloor\frac n{v_n}\right\rfloor, \left\lfloor\frac m{v_m}\right\rfloor \right).$$

因此

$$\sum_{d=1}^{\min(n,m)} f(d) \left\lfloor\frac nd\right\rfloor \left\lfloor\frac md\right\rfloor$$

可以通过 $f$ 的前缀和分块计算。

▶

二维整除分块

ll pre[maxn];

ll calc2( ll n, ll m ) {
    if( n > m ) swap( n, m );

    ll res = 0;
    for( ll l = 1, r; l <= n; l = r + 1 ) {
        ll vn = n / l, vm = m / l;
        r = min( n / vn, m / vm );

        res += ( pre[r] - pre[l - 1] ) * vn * vm;
    }
    return res;
}

只要把 pre 换成对应权函数的前缀和，这段结构就可以复用于互质计数、$\gcd$ 求和、$\gcd^k$ 求和等问题。

3.2 带求和函数的二维分块

有些式子不是直接乘整除商，而是乘

$$S\left(\left\lfloor\frac nd\right\rfloor\right) S\left(\left\lfloor\frac md\right\rfloor\right),$$

其中 $S(x)$ 可能是自然数和、平方和等。

分块边界不变，只需要替换区间贡献。

▶

带权二维整除分块

ll pre[maxn];

ll S( ll n ) { /* 求和公式略 */ }

ll calc2( ll n, ll m ) {
    if( n > m ) swap( n, m );

    ll res = 0;
    for( ll l = 1, r; l <= n; l = r + 1 ) {
        ll vn = n / l, vm = m / l;
        r = min( n / vn, m / vm );

        ll del = pre[r] - pre[l - 1];
        res += del * S( vn ) * S( vm );
    }
    return res;
}

---

4 $\gcd$ 类求和

根据 05_狄利克雷卷积与反演，若令 $g=f*\mu$，则

$$\sum_{i=1}^{n}\sum_{j=1}^{m}f(\gcd(i,j)) = \sum_{d=1}^{\min(n,m)} g(d) \left\lfloor\frac nd\right\rfloor \left\lfloor\frac md\right\rfloor.$$

所以计算问题被统一为：

1. 求出权函数 $g=f*\mu$；
2. 预处理 $g$ 的前缀和；
3. 使用二维整除分块。

4.1 互质数对

取 $f=\varepsilon$，则 $g=\mu$：

$$\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=1] = \sum_{d=1}^{\min(n,m)} \mu(d) \left\lfloor\frac nd\right\rfloor \left\lfloor\frac md\right\rfloor.$$

▶

互质数对

int smu[maxn];

ll cop( ll n, ll m ) {
    if( n > m ) swap( n, m );

    ll res = 0;
    for( ll l = 1, r; l <= n; l = r + 1 ) {
        ll vn = n / l, vm = m / l;
        r = min( n / vn, m / vm );

        res += 1LL * ( smu[r] - smu[l - 1] ) * vn * vm;
    }
    return res;
}

4.2 最大公因数等于 $k$

若 $\gcd(i,j)=k$，令 $i=ka,j=kb$，则 $\gcd(a,b)=1$。

因此

$$\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=k] = \operatorname{cop} \left( \left\lfloor\frac nk\right\rfloor, \left\lfloor\frac mk\right\rfloor \right).$$

对于矩形区间 $[a,b]\times[c,d]$，使用二维前缀容斥：

$$F(b,d)-F(a-1,d)-F(b,c-1)+F(a-1,c-1).$$

▶

矩形区间 gcd 等于 k

ll rect( ll a, ll b, ll c, ll d, ll k ) {
    return cop( b / k, d / k )
         - cop( ( a - 1 ) / k, d / k )
         - cop( b / k, ( c - 1 ) / k )
         + cop( ( a - 1 ) / k, ( c - 1 ) / k );
}

4.3 最大公因数求和

由于 $\operatorname{id}=\varphi*1$，

$$\gcd(i,j)=\sum_{d\mid\gcd(i,j)}\varphi(d).$$

因此

$$\sum_{i=1}^{n}\sum_{j=1}^{m}\gcd(i,j) = \sum_{d=1}^{\min(n,m)} \varphi(d) \left\lfloor\frac nd\right\rfloor \left\lfloor\frac md\right\rfloor.$$

只需要将二维分块中的前缀和替换为

$$\Phi(x)=\sum_{i=1}^{x}\varphi(i).$$

4.4 最大公因数的 $k$ 次幂

令

$$J_k=\operatorname{id}_k*\mu.$$

则 $J_k*1=\operatorname{id}_k$，所以

$$\gcd(i,j)^k = \sum_{d\mid\gcd(i,j)}J_k(d).$$

最终得到

$$\sum_{i=1}^{n}\sum_{j=1}^{m}\gcd(i,j)^k = \sum_{d=1}^{\min(n,m)} J_k(d) \left\lfloor\frac nd\right\rfloor \left\lfloor\frac md\right\rfloor.$$

$J_k$ 是积性函数。若 $p\nmid i$，则 $J_k(ip)=J_k(i)J_k(p)$；若 $p\mid i$，则 $J_k(ip)=p^kJ_k(i)$。

▶

线性筛 Jordan 函数

ll qpow( ll a, ll k, ll mod ) { /* 模板代码略 */ }

int pri[maxn], pcnt;
bool isp[maxn];
ll J[maxn], pre[maxn];
ll K;

void sieve_J( int N ) {
    fill( isp + 2, isp + N + 1, 1 );
    J[1] = pre[1] = 1;

    for( ll i = 2; i <= N; ++ i ) {
        if( isp[i] ) {
            pri[++ pcnt] = i;
            J[i] = ( qpow( i, K, mod ) - 1 + mod ) % mod;
        }

        for( int j = 1; j <= pcnt && i * pri[j] <= N; ++ j ) {
            ll p = pri[j];
            isp[i * p] = 0;

            if( i % p == 0 ) {
                J[i * p] = J[i] * ( J[p] + 1 ) % mod;
                break;
            }
            J[i * p] = J[i] * J[p] % mod;
        }

        pre[i] = ( pre[i - 1] + J[i] ) % mod;
    }
}

4.5 最大公因数为质数

设 $P(n)=[n\text{ 是质数}]$，并令 $g=P*\mu$。

则

$$g(T)=\sum_{p\mid T}\mu\left(\frac Tp\right).$$

预处理时可以枚举质数 $p$，向它的倍数 $T$ 加上 $\mu(T/p)$。

▶

gcd 为质数的权函数

ll pre[maxn];

void init( int N ) {
    for( int j = 1; j <= pcnt; ++ j ) {
        int p = pri[j];

        for( int T = p; T <= N; T += p ) {
            pre[T] += mu[T / p];
        }
    }

    for( int i = 1; i <= N; ++ i ) {
        pre[i] += pre[i - 1];
    }
}

---

5 最小公倍数求和

考虑

$$\sum_{i=1}^{n}\sum_{j=1}^{m}\operatorname{lcm}(i,j).$$

令 $i=da,j=db$，其中 $\gcd(a,b)=1$，则

$$\operatorname{lcm}(i,j)=dab.$$

再用

$$[\gcd(a,b)=1]=\sum_{k\mid a,\;k\mid b}\mu(k)$$

展开互质条件，并把 $T=dk$ 合并，可以得到

$$\sum_{i=1}^{n}\sum_{j=1}^{m}\operatorname{lcm}(i,j) = \sum_{T=1}^{\min(n,m)} h(T) S\left(\left\lfloor\frac nT\right\rfloor\right) S\left(\left\lfloor\frac mT\right\rfloor\right),$$

其中

$$S(x)=\frac{x(x+1)}2,$$

并且

$$h(T)=T\sum_{k\mid T}\mu(k)k.$$

所以需要预处理 $h$ 的前缀和，再使用带权二维分块。

▶

最小公倍数求和的权函数

ll h[maxn], pre[maxn];

void init( int N ) {
    for( int k = 1; k <= N; ++ k ) {
        if( mu[k] == 0 ) continue;

        for( int T = k; T <= N; T += k ) {
            h[T] += 1LL * mu[k] * k;
        }
    }

    for( int T = 1; T <= N; ++ T ) {
        h[T] *= T;
        pre[T] = pre[T - 1] + h[T];
    }
}

若题目要求取模，需要在每次乘法和累加时取模。

---

6 带乘积权值的 $\gcd$ 求和

考虑

$$\sum_{i=1}^{n}\sum_{j=1}^{m}ij\gcd(i,j).$$

令 $i=da,j=db$，其中 $\gcd(a,b)=1$，并展开互质条件，可以得到

$$\sum_{d=1}^{\min(n,m)} d^2\varphi(d) S\left(\left\lfloor\frac nd\right\rfloor\right) S\left(\left\lfloor\frac md\right\rfloor\right).$$

所以需要维护

$$H(x)=\sum_{i=1}^{x}i^2\varphi(i).$$

当数据范围较小时，可以线性筛 $\varphi$ 后直接预处理；当范围过大时，则需要使用加权杜教筛计算 $H(x)$。

---

7 因数个数求和

7.1 二元乘积

有恒等式

$$\tau(ij) = \sum_{a\mid i}\sum_{b\mid j}[\gcd(a,b)=1].$$

对每个质数分别考虑指数即可验证：若 $i$ 与 $j$ 中该质数的指数分别为 $\alpha,\beta$，那么满足 $\min(x,y)=0$ 的指数对共有 $\alpha+\beta+1$ 个，恰好等于 $\tau(p^{\alpha+\beta})$。

展开互质条件后得到

$$\sum_{i=1}^{n}\sum_{j=1}^{m}\tau(ij) = \sum_{d=1}^{\min(n,m)} \mu(d) F\left(\left\lfloor\frac nd\right\rfloor\right) F\left(\left\lfloor\frac md\right\rfloor\right),$$

其中

$$F(x)=\sum_{i=1}^{x}\left\lfloor\frac xi\right\rfloor =\sum_{i=1}^{x}\tau(i).$$

若有多组询问，应该预处理 $F(x)$，而不是在外层分块中重复计算除数求和。

▶

因数个数前缀和

ll f[maxn];

void init( int N ) {
    for( int d = 1; d <= N; ++ d ) {
        for( int x = d; x <= N; x += d ) {
            ++ f[x];
        }
    }

    for( int i = 1; i <= N; ++ i ) {
        f[i] += f[i - 1];
    }
}

▶

约数个数和

ll calc2( ll n, ll m ) {
    if( n > m ) swap( n, m );

    ll res = 0;
    for( ll l = 1, r; l <= n; l = r + 1 ) {
        ll vn = n / l, vm = m / l;
        r = min( n / vn, m / vm );

        ll del = smu[r] - smu[l - 1];
        res += del * f[vn] * f[vm];
    }
    return res;
}

7.2 三元乘积

对于 $\tau(ijk)$，可以继续写成三个因数之间的两两互质条件：

$$\tau(ijk) = \sum_{u\mid i}\sum_{v\mid j}\sum_{w\mid k} [\gcd(u,v)=1] [\gcd(v,w)=1] [\gcd(u,w)=1].$$

展开三个互质条件后，会出现三个莫比乌斯函数和三个最小公倍数：

$$\sum_{x,y,z} \mu(x)\mu(y)\mu(z) F(A,[x,z]) F(B,[x,y]) F(C,[y,z]),$$

其中 $[a,b]$ 表示最小公倍数，并定义

$$F(N,L) = \sum_{q=1}^{\lfloor N/L\rfloor} \left\lfloor\frac{N}{Lq}\right\rfloor.$$

这一结构说明，多元数论求和仍然围绕“展开互质条件、交换求和顺序、计算整除商”展开，但具体优化通常需要针对题目数据范围继续设计。

---

8 杜教筛

8.1 一般形式

设

$$S_f(n)=\sum_{i=1}^{n}f(i).$$

选取一个容易处理的数论函数 $g$，并令

$$h=f*g.$$

那么

$$\sum_{i=1}^{n}h(i) = \sum_{d=1}^{n}g(d) S_f\left(\left\lfloor\frac nd\right\rfloor\right).$$

若 $g(1)=1$，把 $d=1$ 的部分单独提出，就得到

$$S_f(n) = S_h(n) - \sum_{d=2}^{n} g(d) S_f\left(\left\lfloor\frac nd\right\rfloor\right).$$

对右侧按 $\lfloor n/d\rfloor$ 分块，并记 $S_g(x)=\displaystyle\sum_{i=1}^{x}g(i)$：

$$S_f(n) = S_h(n) - \sum_{l=2}^{n} \bigl(S_g(r)-S_g(l-1)\bigr) S_f\left(\left\lfloor\frac nl\right\rfloor\right).$$

递归过程中只会访问形如 $\lfloor n/i\rfloor$ 的值，因此可以使用哈希表记忆化。

8.2 莫比乌斯函数前缀和

因为

$$\mu*1=\varepsilon,$$

取 $f=\mu,g=1,h=\varepsilon$。

当 $n\ge1$ 时，$\displaystyle\sum_{i=1}^{n}\varepsilon(i)=1$，所以

$$M(n) = 1- \sum_{l=2}^{n} (r-l+1) M\left(\left\lfloor\frac nl\right\rfloor\right),$$

其中 $M(n)=\displaystyle\sum_{i=1}^{n}\mu(i)$。

8.3 欧拉函数前缀和

因为

$$\varphi*1=\operatorname{id},$$

取 $f=\varphi,g=1,h=\operatorname{id}$。

因此

$$\Phi(n) = \frac{n(n+1)}2 - \sum_{l=2}^{n} (r-l+1) \Phi\left(\left\lfloor\frac nl\right\rfloor\right),$$

其中 $\Phi(n)=\displaystyle\sum_{i=1}^{n}\varphi(i)$。

▶

杜教筛求 mu 与 phi 前缀和

int smu[maxn];
ll sph[maxn];

unordered_map<ll, ll> mmu, mph;

ll S1( ll n ) {
    return n * ( n + 1 ) / 2;
}

ll M( ll n ) {
    if( n < maxn ) return smu[n];
    if( mmu.count( n ) ) return mmu[n];

    ll res = 1;
    for( ll l = 2, r; l <= n; l = r + 1 ) {
        ll v = n / l;
        r = n / v;

        res -= ( r - l + 1 ) * M( v );
    }
    return mmu[n] = res;
}

ll P( ll n ) {
    if( n < maxn ) return sph[n];
    if( mph.count( n ) ) return mph[n];

    ll res = S1( n );
    for( ll l = 2, r; l <= n; l = r + 1 ) {
        ll v = n / l;
        r = n / v;

        res -= ( r - l + 1 ) * P( v );
    }
    return mph[n] = res;
}

这里默认 smu 与 sph 已通过线性筛预处理。

8.4 加权杜教筛

杜教筛并不只适用于 $\mu$ 和 $\varphi$。

令

$$f(n)=n^2\varphi(n),\qquad g(n)=n^2.$$

则

$$(f*g)(n) = \sum_{d\mid n} d^2\varphi(d) \left(\frac nd\right)^2 = n^2\sum_{d\mid n}\varphi(d) = n^3.$$

也就是

$$(n^2\varphi)*\operatorname{id}_2 = \operatorname{id}_3.$$

若记

$$H(n)=\sum_{i=1}^{n}i^2\varphi(i),$$

那么

$$H(n) = \sum_{i=1}^{n}i^3 - \sum_{l=2}^{n} \left( \sum_{d=l}^{r}d^2 \right) H\left(\left\lfloor\frac nl\right\rfloor\right).$$

▶

加权杜教筛求 i²phi(i) 前缀和

ll S2( ll n ) { /* 平方和公式略 */ }
ll S3( ll n ) { /* 立方和公式略 */ }

ll pre[maxn];
unordered_map<ll, ll> mp;

ll H( ll n ) {
    if( n < maxn ) return pre[n];
    if( mp.count( n ) ) return mp[n];

    ll res = S3( n );
    for( ll l = 2, r; l <= n; l = r + 1 ) {
        ll v = n / l;
        r = n / v;

        ll del = S2( r ) - S2( l - 1 );
        res -= del * H( v );
    }
    return mp[n] = res;
}

若在模意义下计算，只需将求和公式与乘法改为对应的模运算。

---

9 方法选择

数据与目标	常用方法
单次计算 $\sum\lfloor n/i\rfloor$	一维整除分块
已知权函数前缀和，计算二维式子	二维整除分块
多组中小范围询问	线性筛权函数并预处理前缀和
$\gcd$ 类权值	先求 $g=f*\mu$
$\operatorname{lcm}$ 或乘积权值	展开互质条件并重新构造权函数
范围超出筛法上限，求 $\sum\mu$、$\sum\varphi$	杜教筛
求加权数论函数前缀和	寻找合适卷积等式后使用加权杜教筛

实际复杂度不仅取决于公式，还取决于询问次数、预处理上限、模数和所需前缀函数是否能够快速求出。

---

10 与后续内容的联系

• 数论求和依赖数论函数、积性、狄利克雷卷积和莫比乌斯反演；
• 整除分块负责批量处理相同的整除商；
• 杜教筛负责计算超出线性筛范围的数论函数前缀和；
• 组合数取模会继续使用逆元、质数幂分解与 CRT；
• 大整数分解则转向 Miller–Rabin 与 Pollard–Rho。

相关内容：

• 03_数论函数与线性筛
• 05_狄利克雷卷积与反演
• 07_组合数取模