题意简析
求一个子段和 \(S_{i,j}\)，满足 \(S_{i,j} \equiv x \pmod{p}\)，\(x \geq k\)，并且使这个模值最小。其中，\(S_{i,j}\) 是子段 \(a_i\) 到 \(a_j\) 的和。
思路解析
看到题目和区间、求和相关，\(n\) 也比较大，于是我们显然可以想到前缀和算法。定义前缀和数组 \(sum\)，其中 \(sum_0 =0\)，\(sum_i \equiv sum_{i-1} + a_i\pmod{p}\)。这样，子段和 \(S_{i,j}\) 可以表示为 \(sum_j - sum_{i-1}\) 的模运算结果。
但是由于模意义下并不单调，我们需要分类讨论：
-
当 \(x \ge y\) 时，模值为 \(x - y\)。需要满足 \(x - y \ge k\)，即 \(y \le x - k\)。为了最小化 \(x - y\)，应在区间 \([0, x - k]\) 中寻找最大的 \(y\)。
-
当 \(x < y\) 时，模值为 \(x - y + p\)。需要满足 \(x - y + p \ge k\)，即 \(y \le x + p - k\)。为了最小化 \(x - y + p\)，应在区间 \((x, \min(x + p - k, p - 1)]\) 中寻找最大的 \(y\)。
使用 std::set 维护之前出现的前缀和模值，使用二分查找，查询区间最大值。
时间复杂度：\(O(n \log n)\)。
代码实现
十年 OI 一场空，不开
long long见祖宗！
#pragma G++ optimize("O3", "unroll-loops", "omit-frame-pointer", "inline")
#include <bits/stdc++.h>
using namespace std;typedef long long ll;
int a[100005],sum_mod[100005];
int main() {ios::sync_with_stdio(false);cin.tie(0);ll n, k, p;cin >> n >> k >> p;for (int i = 1; i <= n; i++) {cin >> a[i];}set<ll> s;s.insert(0);ll ans = p; // 初始化为 p（因为答案不会超过 p-1）for (int i = 1; i <= n; i++) {sum_mod[i] = (sum_mod[i - 1] + a[i]) % p;if (sum_mod[i] < 0) {sum_mod[i] += p;}ll x = sum_mod[i];ll cand1 = -1; // 候选值1ll cand2 = -1; // 候选值2// 情况1：x >= y，在 [0, x - k] 中找最大 yif (x >= k) {auto it = s.upper_bound(x - k);if (it != s.begin()) {it--;cand1 = x - *it;}}// 情况2：x < y，在 (x, min(x + p - k, p - 1)] 中找最大 yll R = x + p - k;if (R > p - 1) {R = p - 1;}if (R > x) { // 区间非空auto it = s.upper_bound(R);if (it != s.begin()) {it--;if (*it > x) { // 确保 y 在区间 (x, R] 内cand2 = x - *it + p;}}}// 更新答案if (cand1 != -1) {ans = min(ans, cand1);}if (cand2 != -1) {ans = min(ans, cand2);}s.insert(x);}cout << ans << endl;return 0;
}