我们考虑暴力枚举的方法，枚举所有子段，并利用循环求和，判断和是否为 K的倍数。其中枚举子段是 O(n^2)的，求和是 O(n) 的，因此总的复杂度为 O(n^3)
如果我们利用前缀和数组，通过预处理，可以 O(1)时间计算一段区间的和，这样复杂度可以优化到 O(n^2) 。
我们思考，如果某一个子段 (i,j)的和是 K的倍数。那么 i−1和 j的前缀和 %K一定同余。所以我们统计所有前缀和 %K 的结果。用 cnt数组记录同余的数量。其中 cnti中记录的是前缀和 %K=i的有多少个。
再用组合数 C(cnti,2) 来计算有多少对同余，最终对所有结果求和即可。由于 K的范围只有 1w 。可以利用数组进行计数，这样最终的复杂度为 O(n+K)。