自动搬运

查看原文

来自洛谷，原作者为

	Yxa_Sheep 打表过样例，暴力出奇迹，搜索真牛逼，骗分进省一||深搜 MLE，广搜 TLE，打表 RE，退火又 CE||删掉 display 看主页||被封取关（解封后私信）||六年级蒟蒻 ，代词请用“他”||当前状态：<离线>

搬运于2025-08-24 21:18:34，当前版本为作者最后更新于2025-06-26 14:13:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

题意

找出和能被 $k$ 整除的最长子串中起始位置最靠后的数列，输出它的长度和其中的每个数。

思路

题目还没看完，就眼前就自动浮现了三个字：前缀和。两个除以 $k$ 余数相同的数相减一定能被 $k$ 整除（就当余数抵消了吧）。这时，我们可以用 map 维护每一个余数第一次出现的位置（$k$ 有点大，怕数组塞不下），如果出现了同样的余数并且长度大于等于 $len$（用来存储最终长度），就更新 $len$ 的值。细节在代码中注释了。

代码

#include <bits/stdc++.h>
using namespace std;
int n, k, len = -1, l, r, sum, a[100010];
map<int, int> mp;
int main()
{
    scanf("%d%d", &n, &k);
    mp[0] = 0; //一定要把 mp[0] 初始化为 0，相当于从 1 开始选
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        sum = (sum + a[i]) % k;
        if (!mp.count(sum)) //如果没有这个键
            mp[sum] = i;
        else if (i - mp[sum] >= len)
            len = i - mp[sum], l = mp[sum] + 1, r = i;
    }
    printf("%d\n", len); //我的 len 初始化为 -1 了哈
    for (int i = l; i <= r && len != -1; i++) // 条件要加 len != -1
        printf("%d ", a[i]);
    return 0;
}

题解来之不易，且看且珍惜。给个赞再走吧。

题目传送门