题解 | #K序列#

本人第一次编写题解，如果有错误还请大家多多海涵 对于这道题，我们可以采用一种很巧妙的算法，即 “如果前i个数的前缀和与前j个数的前缀和(在对k取余之后)相等，则从i到j之间的数的和都为k的倍数”

using namespace std;
int main() {
    int n, K;
    cin >> n >> K;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    unordered_map<int, int>t;
    t[0] = 0;  // 初始化：前缀和为0的位置记为0（前0个元素）
    int prefix = 0;  // 当前前缀和的模
    int max_len = 0;

    for (int i = 1; i <= n; ++i) {  // i表示前i个元素的前缀和（对应数组0..i-1）
        // 累加当前元素并取模，确保结果非负
        prefix = (prefix + a[i - 1]) % K;
        // 若该模值已出现过，计算子数组长度
        if (t.count(prefix)) {
            max_len = max(max_len, i - t[prefix]);
        } else {
            // 首次出现，记录位置
            t[prefix] = i;
        }
    }

    cout << max_len << endl;
    return 0;
}