alt 题目如上：

题解：

题目意思

给你 n 个数字和一个数 p，要找一个连续的子段，使得这个子段的和除以 p 的余数最大。

比如数组 [3,4,5,6,7]，p=10；选子段 [2,3]，和是 4+5=9，9%10=9，余数最大，输出：2 3 9

关键想法

1. 用前缀和简化

子段 [l, r]的和除以 p 的余数是：

(S[r] - S[l-1]) % p

2. 怎么找最大的余数？

对每个位置 r（当作子段终点），我们要找一个位置 l-1（在 r 之前），让 (S[r] - S[l-1]) % p最大。

两种情况：

1.如果 S[r] ≥ 某个之前的 S[i]，选最小的 S[i] → 余数 = S[r] - S[i]

2.如果 S[r] < 某个之前的 S[i]，选大于 S[r] 的最小 S[i] → 余数 = S[r] - S[i] + p

实际上两种情况可以合并为：

余数 = (S[r] - S[i] + p) % p

我们要让这个余数最大。

算法步骤

  • 用一个 map 存之前见过的前缀和值，以及它们最早出现的位置

  • 左到右遍历数组，计算当前前缀和 S

  • 在 map 里找：

  • 如果有大于 S 的数，选最小的那个

  • 如果没有，选最小的数

  • 用公式算出余数，更新最大余数

  • 如果当前 S 没在 map 里，把它加进去（记下当前位置）

  • 最后输出最大余数和对应的子段位置

AC码如下：

void solve() {
	int n, p, sum = 0, i;
	cin >> n >> p;
	map<int, int> mp;
	array<int, 3> ans = {0, 0, 0}; // {余数, 起点, 终点}
	mp[0] = 0;
	for (i = 1; i <= n; i++) {
		int num;
		cin >> num;
		sum = (sum + num) % p;
		auto it = mp.upper_bound(sum);
		int key;
		if (it == mp.end())
			key = mp.begin()->first;
		else
			key = it->first;
		int value = (sum - key + p) % p;
		array<int, 3> a = {value, mp[key], i - 1};
		ans = max(ans, a);//用array可以直接求，方便
		if (mp.find(sum) == mp.end())
			mp[sum] = i;
	}
	cout << ans[1]  << " " << ans[2] << " " << ans[0] << endl;
}

signed main() {
	//vector<vector<int>>a(n,vector<int>(m)); 二维构造
	//cout << fixed << setprecision(10);  固定小数输出
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int T = 1;
//	cin >> T;
	while (T--) solve();
	return 0;
}

如有错误感谢指出和纠正！