P8649 [蓝桥杯 2017 省 B] k 倍区间

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 读取输入的整数 n 和 k
        int n = sc.nextInt(); // 数组长度
        int k = sc.nextInt(); // 取模的值
        
        // 创建一个数组存储输入的整数
        int[] nums = new int[n];
        
        // 计算前缀和的总和
        long sum = 0;
        // 统计满足条件的个数
        long count = 0;
        
        // 创建一个数组来统计每个余数的出现次数
        long[] remainderCount = new long[k];
        
        // 初始状态下，余数为 0 的情况有 1 种，要先把 0 % k = 0 这种情况给算进去
        remainderCount[0] = 1;
        
        // 读取输入的整数，并计算前缀和的余数
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
            sum += nums[i]; // 计算前缀和
            int r = (int) (sum % k); // 计算当前前缀和对 k 取模的结果
            remainderCount[r]++; // 统计余数出现次数
        }
        
        // 遍历不同余数出现的次数
        for (int i = 0; i < k; i++) {
            // 相同余数中任取两个，他们所对应的区间是满足条件的
            count += remainderCount[i] * (remainderCount[i] - 1) / 2;
        }
        
        // 输出结果
        System.out.println(count);
    }
}