[模板] 整除分块（数论分块）

一般形式

数论分块一般用于计算下列式子的值

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

如果使用暴力扫描的方式，时间复杂度是 $O(n)$ 的，而通过暴力打表的方式，我们发现对于每一个 $i$，$\frac{n}{i}$ 的取值最多只有 $2 \sqrt{n}$ 种。

整除分块

对于 $i \in \left [i , \lfloor \frac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor \right ] $，它们 $\lfloor \frac{n}{i} \rfloor$ 的值是一样的。

令 $j = \lfloor \frac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor $，显然有

$$ j = \lfloor \frac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor \leq \frac{n}{\lfloor \frac{n}{i} \rfloor} < j+1 $$

因此

$$
\begin{cases}
\lfloor \frac{n}{i} \rfloor \leq \frac{n}{j} \\
\frac{n}{j+1} < \lfloor \frac{n}{i} \rfloor
\end{cases}
$$

因此 $j$ 是最大取值

for (register int i=1; i <= n; i = j + 1){
    j = n / ( n / i ),
    ans += 1 * (j - i + 1) * (n / i);
}

例题一 2017美团资格赛 A

题目描述

给定两个整数 $l$ 和 $r$。

对于任意 $x$，满足 $l \leq x \leq r$，把 $x$ 的所有约数全部写下来。

对于每个写下来的数，只保留最高位的那个数码。求 $[1,9]$ 中每个数码出现的次数。

解题思路

分别处理数码 $[1, 9]$ 的出现次数，而这个次数具有可减性，因此可以用 $1 – r$ 的和减去 $1 – (l-1)$ 的和

而约数的数码只和最高位有关，因此对于数码 $1$ ，那么它只可能是 $1$, $10 \cdots 19$, $100 \cdots 199$ 等，是一个区间段，可以通过整除分块解决

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

inline int read(){
    int x = 0;
    char ch = getchar();

    while(ch < '0' || ch > '9')
        ch = getchar();

    while('0' <= ch && ch <= '9'){
        x = x*10 + ch - '0';
        ch = getchar();
    }

    return x;
} 

int l, r;

inline long long calc2(long long n, long long a, long long b){
    long long ans = 0;
    long long j = 0;

    for(register long long i=a; i <= b; i = j + 1){
        j = min(b, n / (n / i));
        ans += 1ll * (j - i + 1) * (n / i);
    }

    return ans;
}

inline long long calc(long long n, long long num){
    long long range = 1;
    long long ans = 0;

    for(; n >= num; range *= 10, num *= 10){
        ans += calc2(n, num, min(n, num + range - 1));
    }

    return ans;
}
int main(){
    l = read();
    r = read();

    for(register int i=1; i<=9; i++){
        printf("%lld\n", calc(r, i) - calc(l-1, i));
    }

    return 0;
}

例题二 [CQOI2007]余数之和

题目描述

给出两个正整数 $n$ 和 $k$，计算
$f(n, k) = k \ mod \ 1 + k \ mod \ 2 + k \ mod \ 3 + … + k \ mod \ n$的值

解题思路

式子可化为
$$
\begin{aligned}
f(n, k) &= \sum_{i=1}^n (k – i * \lfloor \frac{k}{i} \rfloor) \\
&= n * k – \sum_{i=1}^n i * \lfloor \frac{k}{i} \rfloor
\end{aligned}
$$

右边可以使用整除分块来处理，对于 $[i, j]$，它们的 $\lfloor \frac{k}{i} \rfloor$ 相同，而 $i…j$ 是一个等差数列

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

inline int read(){
    int x = 0;
    char ch = getchar();

    while(ch < '0' || ch > '9')
        ch = getchar();

    while('0' <= ch && ch <= '9'){
        x = x*10 + ch - '0';
        ch = getchar();
    }

    return x;
}

long long n, k;

inline long long calc(){
    long long j;
    long long ans = 0;

    for(register long long i = 1; i <= min(n, k); i = j + 1){
        j = min(n, k / (k / i));
        ans += (i + j) * (j - i + 1) / 2 * (k / i);
    }

    return ans;
}

int main(){
    n = read();
    k = read();

    printf("%lld", n * k - calc());

    return 0;
}