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

### 一般形式

$$\sum_{i=1}^n \lfloor \frac{n}{i} \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}$$

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


### 例题一 2017美团资格赛 A

#### 解题思路

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

using namespace std;

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(){

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

return 0;
}


### 例题二 [CQOI2007]余数之和

#### 题目描述

$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}

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

using namespace std;

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(){