题解：P15566 [COCI 2025/2026 #5] 重量 / Težina

· · 题解

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

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

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

整除分块

引一个例子来理解：

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

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

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

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

发现了吗，在后大半段时结果大都为 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;
}

::::