整除分块（数论分块）

文章基于b站大佬的视频——整除分块 by泥土笨笨

求

∑ i = 1 n ⌊ n i ⌋ sum_{i=1}^{n}{left lfloor frac{n}{i} right rfloor} i=1∑n​⌊in​⌋

其中 n ≤ 1 0 12 nle10^{12} n≤1012，我们打表观察下规律

以 n = 10 n=10 n=10为例，表中同样的值会连续出现，而相同的值所划分的区间积是整出分块。整除的性质使得从1到n的 ⌊ n i ⌋ left lfloor frac{n}{i} right rfloor ⌊in​⌋可根据数值划分为不同的分块，且分块数远远小于n。利用这种性质，我们如果能推导出每个分块具体的左右端点位置在哪，这个问题就可以快速求解出来了。

性质1： ⌊ n i ⌋ left lfloor frac{n}{i} right rfloor ⌊in​⌋最多只有 2 n 2sqrt{n} 2n ​种取值

证明：对于 i ≤ n ile sqrt{n} i≤n ​，最多只有 n sqrt{n} n ​种取值，而对于 i > n i>sqrt{n} i>n ​，有 n i < n frac{n}{i}

性质2: 若 ⌊ n r ⌋ left lfloor frac{n}{r} right rfloor ⌊rn​⌋与 ⌊ n i ⌋ left lfloor frac{n}{i} right rfloor ⌊in​⌋相等，那么 r r r的最大取值为
⌊ n ⌊ n i ⌋ ⌋ left lfloor frac{n}{left lfloor frac{n}{i} right rfloor} right rfloor ⌊⌊in​⌋n​⌋

证明：设 ⌊ n i ⌋ = k left lfloor frac{n}{i} right rfloor=k ⌊in​⌋=k，于是如果 r r r取到比较大的数字，使得 ⌊ n r ⌋ left lfloor frac{n}{r} right rfloor ⌊rn​⌋与 ⌊ n i ⌋ left lfloor frac{n}{i} right rfloor ⌊in​⌋不相等，那么 ⌊ n r ⌋ < k left lfloor frac{n}{r} right rfloor < k ⌊rn​⌋ n k r>frac{n}{k} r>kn​，那么 r > ⌊ n k ⌋ r>left lfloor frac{n}{k} right rfloor r>⌊kn​⌋，即 r > ⌊ n ⌊ n i ⌋ ⌋ r>left lfloor frac{n}{left lfloor frac{n}{i} right rfloor} right rfloor r>⌊⌊in​⌋n​⌋。所以 r r r最大取到 ⌊ n ⌊ n i ⌋ ⌋ left lfloor frac{n}{left lfloor frac{n}{i} right rfloor} right rfloor ⌊⌊in​⌋n​⌋可以使得 ⌊ n r ⌋ left lfloor frac{n}{r} right rfloor ⌊rn​⌋与 ⌊ n i ⌋ left lfloor frac{n}{i} right rfloor ⌊in​⌋相等

代码演示：

for(int l = 1;l <= n;l = r + 1) {
	r = n / (n / l);
}

已知正整数 n , a , b n,a,b n,a,b，求
∑ i = 1 n ⌊ n a i + b ⌋ sum_{i=1}^{n}{left lfloor frac{n}{ai+b} right rfloor} i=1∑n​⌊ai+bn​⌋
证明：设 ⌊ n a i + b ⌋ = k left lfloor frac{n}{ai+b} right rfloor=k ⌊ai+bn​⌋=k，于是如果 r r r取到比较大的数字，使得 ⌊ n a r + b ⌋ left lfloor frac{n}{ar+b} right rfloor ⌊ar+bn​⌋与 ⌊ n a i + b ⌋ left lfloor frac{n}{ai+b} right rfloor ⌊ai+bn​⌋不相等，那么 ⌊ n a r + b ⌋ < k left lfloor frac{n}{ar+b} right rfloor < k ⌊ar+bn​⌋ n − k b a k r>frac{n-kb}{ak} r>akn−kb​，那么 r > ⌊ n − k b a k ⌋ r>left lfloor frac{n-kb}{ak} right rfloor r>⌊akn−kb​⌋。所以 r r r最大取到 ⌊ n − k b a k ⌋ left lfloor frac{n-kb}{ak} right rfloor ⌊akn−kb​⌋时 ⌊ n a r + b ⌋ = ⌊ n a i + b ⌋ left lfloor frac{n}{ar+b} right rfloor=left lfloor frac{n}{ai+b} right rfloor ⌊ar+bn​⌋=⌊ai+bn​⌋.

P2261 [CQOI2007]余数求和

给出正整数 n n n 和 k k k，请计算

G ( n , k ) = ∑ i = 1 n k   m o d   i G(n, k) = sum_{i = 1}^n k bmod i G(n,k)=i=1∑n​kmodi

其中 k   m o d   i kbmod i kmodi 表示 k k k 除以 i i i 的余数。

输入只有一行两个整数，分别表示 n n n 和 k k k。

输出一行一个整数表示答案。

10 5

29

G ( 10 , 5 ) = 0 + 1 + 2 + 1 + 0 + 5 + 5 + 5 + 5 + 5 = 29 G(10, 5)=0+1+2+1+0+5+5+5+5+5=29 G(10,5)=0+1+2+1+0+5+5+5+5+5=29。

• 对于 30 % 30% 30% 的数据，保证 n , k ≤ 1 0 3 n , k leq 10^3 n,k≤103。
• 对于 60 % 60% 60% 的数据，保证 n , k ≤ 1 0 6 n, k leq 10^6 n,k≤106。
• 对于 100 % 100% 100% 的数据，保证 1 ≤ n , k ≤ 1 0 9 1 leq n, k leq 10^9 1≤n,k≤109。

首先，我们知道
k % i = k − i ⌊ k i ⌋ k%i=k-i left lfloor frac{k}{i} right rfloor k%i=k−i⌊ik​⌋
所以
∑ i = 1 n k   m o d   i = ∑ i = 1 n ( k − i ⌊ k i ⌋ ) = ∑ i = 1 n k − ∑ i = 1 n i ⌊ k i ⌋ = n k − ∑ i = 1 n i ⌊ k i ⌋ sum_{i=1}^{n}{k mod i}=sum_{i=1}^{n}{(k-ileft lfloor frac{k}{i} right rfloor)}=sum_{i=1}^{n}{k}-sum_{i=1}^{n}{ileft lfloor frac{k}{i} right rfloor}=nk-sum_{i=1}^{n}{ileft lfloor frac{k}{i} right rfloor} i=1∑n​k mod i=i=1∑n​(k−i⌊ik​⌋)=i=1∑n​k−i=1∑n​i⌊ik​⌋=nk−i=1∑n​i⌊ik​⌋
而
∑ i = 1 n i ⌊ k i ⌋ sum_{i=1}^{n}{ileft lfloor frac{k}{i} right rfloor} i=1∑n​i⌊ik​⌋
可以用除法分块来求，每次求一个 ⌊ k i ⌋ left lfloor frac{k}{i} right rfloor ⌊ik​⌋值固定的区间 [ l , r ] [l,r] [l,r]，这时候把 ⌊ k i ⌋ left lfloor frac{k}{i} right rfloor ⌊ik​⌋提出来，剩下部分是一个等差数列，直接用公式求和，再乘以 ⌊ k i ⌋ left lfloor frac{k}{i} right rfloor ⌊ik​⌋即可

#include
using namespace std;
typedef long long ll;
int main()
{
    ll n, k, r, l;
    cin >> n >> k;
    ll ans = n * k;
    for (l = 1, r; l <= n; l = r + 1) {
        if (k / l == 0) break;
        r = min(n, k / (k / l));
        ans -= (k / l) * (l + r) * (r - l + 1) / 2;
    }
    cout << ans;
    return 0;
}

P6003 [USACO20JAN] Loan Repayment S

Farmer John 欠了 Bessie N N N 加仑牛奶（ 1 ≤ N ≤ 1 0 12 1 leq N leq 10^{12} 1≤N≤1012）。他必须在 K K K 天内将牛奶给 Bessie。但是，他不想将牛奶太早拿出手。另一方面，他不得不在还债上有所进展，所以他必须每天给 Bessie 至少 M M M 加仑牛奶（ 1 ≤ M ≤ 1 0 12 1 leq M leq 10^{12} 1≤M≤1012）。

以下是 Farmer John 决定偿还 Bessie 的方式。首先他选择一个正整数 X X X。然后他每天都重复以下过程：

1. 假设 Farmer John 已经给了 Bessie G G G 加仑，计算 N − G X frac{N-G}{X} XN−G​ 向下取整。令这个数为 Y Y Y。
2. 如果 Y Y Y 小于 M M M，令 Y Y Y 等于 M M M。
3. 给 Bessie Y Y Y 加仑牛奶。

求 X X X 的最大值，使得 Farmer John 按照上述过程能够在 K K K 天后给 Bessie 至少 N N N 加仑牛奶 （ 1 ≤ K ≤ 1 0 12 1 leq K leq 10^{12} 1≤K≤1012）。

输入仅有一行，包含三个空格分隔的正整数 N , K , M N,K,M N,K,M，满足 K × M < N K times M 输出格式

输出最大的正整数 X X X，使得按照上述过程 Farmer John 会给 Bessie 至少 N N N 加仑牛奶。

10 3 3

2

在这个测试用例中，当 X = 2 X=2 X=2 时 Farmer John 第一天给 Bessie 5 5 5 加仑，后两天每天给 Bessie M = 3 M=3 M=3 加仑。

• 测试点 2 ∼ 4 2 sim 4 2∼4 满足 K ≤ 1 0 5 K leq 10^5 K≤105。
• 测试点 5 ∼ 11 5 sim 11 5∼11 没有额外限制。

题目中说求 X X X的最大值，那么直接对其二分即可， X X X越大还完牛奶的天数越长，显然满足二分单调性。

对于二分的 c h e c k check check函数，设 g g g是现在已经还的牛奶量，那么今天要还的 y = n − g x y=frac{n-g}{x} y=xn−g​，假设持续 d d d天，每天都还这么多，那么有
⌊ n − g − y d x ⌋ = y left lfloor frac{n-g-yd}{x} right rfloor=y ⌊xn−g−yd​⌋=y
去掉取整符号，也就是
n − g − y d x ≥ y frac{n-g-yd}{x} ge y xn−g−yd​≥y
整理一下可以得到
d ≤ n − g − x y y d le frac{n-g-xy}{y} d≤yn−g−xy​
所以 d d d最大可以取到
⌊ n − g − x y y ⌋ left lfloor frac{n-g-xy}{y} right rfloor ⌊yn−g−xy​⌋
注意，当 d = 0 d=0 d=0时说明只能还今天的，第二天需要还的牛奶量就不一样了，所以实际上分块的大小为 d + 1 d+1 d+1

#include
#include
#include
#include
#include
#include
#include
#include