congruence modulo

主要是一道 “初等数论同余在滑动窗口中的应用” 的题想到的

本质：

1. 变形为子数组求和 - 前缀和预处理
2. 滑动窗口左右端点根据同余的性质移项到两边
3. 枚举右维护左
4. 左边用哈希表记录（有限值 - 缩短为数组）

证明： Congruence Modulo

难度值：2073

T

A

// C++

class Solution {
public:
    long long countInterestingSubarrays(vector<int>& nums, int modulo, int k) {
        int n = nums.size();
        vector<int> sum(n + 1);
        for (int i = 0; i < n; i++) {
            sum[i + 1] = sum[i] + (nums[i] % modulo == k);
        }

        vector<int> cnt(min(n + 1, modulo));
        long long res = 0;
        for (int s : sum) {
            if (s >= k) {
                res += cnt[(s - k) % modulo];
            }
            cnt[s % modulo]++;
        }
        return res;
    }
};