#include<bits/stdc++.h>
using namespace std;
 
typedef long long LL;
const int N = 1e5 + 10;
const LL P = 1e8;
 
LL a[N];
 
int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	LL n, K;
	cin >> n >> K;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
	}
	LL ans = 0;
	for (int j = 1; j <= n; j ++) {
		LL sum = 0;
		LL t = 1;
		while (t <= K && t <= a[j]) {
			LL ii = a[j] / t;
			LL si = min(K, a[j] / ii);
			sum += (si - t + 1) * min(ii * (a[j] + 2), P);
			t = si + 1;
		}
		ans += sum;
	}
	cout << ans << "\n";
	
	return 0;
} 

题意

给定正整数 $n,k$ 和长为 $n$ 的序列 $a$，求：

$$\sum_{p=1}^k\sum_{i=1}^n\min(10^8,\lfloor \frac{a_i}{p}\rfloor\times (a_i+2))$$

思路

考虑到如何把第一个和式简化掉，我们可以试着列出所有的 $\lfloor \frac{n}{i}\rfloor$，其中 $i\in[1,n]$。这里我们设 $n=30$，那么可以列出这么一张表：

1 30
2 15
3 10
4 7
5 6
6 5
7 4
8 3
9 3
10 3
11 2
12 2
13 2
14 2
15 2
16-30 1

不难发现，有几段他们的商是一样的，而且我可以确切的告诉你，块的数量是 $\sqrt n$ 级别的，这便是我们今天的主角——整除分块。

整除分块

虽说名字里带分块，但是与正宗的数列分块还是值域分块相比，都要简单很多。跟上面的例子一样，我们把商相同的除数归为一块，可以将时间复杂度从 $O(n)$ 降至 $O(\sqrt n)$。

块的大小

对于 $i\le \sqrt n$：此时块的个数最多是 $\sqrt n$，即每个 $i$ 单独一块。

对于 $i> \sqrt n$：此时块的个数最多也是 $\sqrt n$，因为 $\lfloor \frac{n}{i}\rfloor$ 肯定是小于等于 $\sqrt n$ 的。根据定义，所以块的个数也是 $\sqrt n$ 级别的。

块的端点

对于一个块，如果他的左端点为 $l$，那么块的值 $x=\lfloor \frac{n}{l}\rfloor$。那么根据定义，块的右端点 $r$ 满足 $r\times x\le n$，所以 $r=\lfloor \frac{n}{x}\rfloor=\lfloor \frac{n}{\lfloor \frac{n}{l}\rfloor}\rfloor$。

所以这题就是整除分块的模板了吧。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k,x,sum;
signed main(){
    cin>>n>>k;
    while(n--){
        cin>>x;
        for(int l=1;l<=min(x,k);){
            int r=min(x/(x/l),min(x,k));
            sum+=(r-l+1)*min(100000000ll,(x/l)*(x+2));
            l=r+1;
        }
    }
    cout<<sum;
    return 0;
}

结语

总结一下，整除分块并没有我们想象的那么难，结论非常好推，而且不会推肯定也能记住，算是数论里比较简单了的了。

另外本题还存在时间复杂度更优的树状数组解法，留给读者思考。

如果题解有问题，请私信我，我会在讨论区更正。

本题前置知识点：整除分块。

如果你已经会了整除分块，请跳过下面的内容。

---

整除分块

引一个例子来理解：

如下有一道例题，请你用编程实现：

给你一个整数 $n$，请你输出一个长度为 $n$ 的数列 $a_1,a_2,\dots,a_n$，$a_i$ 表示对于 $1$ 到 $n$ 中每一个数，哪些数除 $n$ 向下取整的结果等于 $i$。

如果在 $1 \le n \le 10^9$ 的情况下，那么一个一个数遍历的思路就不可实现，这时候，我们可以用整除分块。

拿 $10$ 举例，我们来观察一下一般怎么实现：

• $\lfloor 10 \div 1 \rfloor = 10$，$a_{10}$ 的值加一；
• $\lfloor 10 \div 2 \rfloor = 5$，$a_{5}$ 的值加一；
• $\lfloor 10 \div 3 \rfloor = 3$，$a_{3}$ 的值加一；
• $\lfloor 10 \div 4 \rfloor = 2$，$a_{2}$ 的值加一；
• $\lfloor 10 \div 5 \rfloor = 2$，$a_{2}$ 的值加一；
• $\lfloor 10 \div 6 \rfloor = 1$，$a_{1}$ 的值加一；
• $\lfloor 10 \div 7 \rfloor = 1$，$a_{1}$ 的值加一；
• $\lfloor 10 \div 8 \rfloor = 1$，$a_{1}$ 的值加一；
• $\lfloor 10 \div 9 \rfloor = 1$，$a_{1}$ 的值加一；
• $\lfloor 10 \div 10 \rfloor = 1$，$a_{1}$ 的值加一。

发现了吗，在后大半段时结果大都为 $1$，程序会将这些冗余的情况全部遍历一遍，所以比如 $i$ 第一次使商为某个数时我们可以计算 $\lfloor n \div \lfloor n \div i \rfloor \rfloor$ 什么时候结果最后一次为 $\lfloor n \div i \rfloor$，计算出来后将下表快速移动就可以降低时间复杂度。

---

接下来我们来看怎么做这道题。

这道题让我们求：

$$\sum_{i=1}^{n} \sum_{j=1} ^ {k} \min(\lfloor a_i \div j\rfloor \times (a_i + 2) ,10^8)$$

那么我们最外面的求和符号（即 $\sum_{i=1}^{n}$）可以用一层 for 循环实现，对于里面一层，不就和我们刚才说的例题完全一致吗？

时间复杂度 $O(nk) \rightarrow O(n\sqrt{k})$，可以通过。

::::success[AC代码]

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e8;
int a[100001];
signed main() {
	int n, k, ans = 0;
	cin >> n >> k;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for(int i = 1; i <= n; i++) {
		int x = a[i] + 2;
		int t = 1;
		while(t <= k && t <= a[i]) {
			int l = a[i] / t;
			int r = min(k, a[i] / l);
			ans += min(N, l * x) * (r - t + 1);
			t = r + 1;
		}
	}
	cout << ans;
	return 0;
}

::::