计算总和可被k整除的所有子数组

在本教程中，我们将讨论一个程序，以找到总和可被k整除的子数组的数量。

为此，我们将提供一个数组和一个值k。我们的任务是找到总和等于给定值k的子数组的数量。

示例

#include <bits/stdc++.h>
using namespace std;
//用k sum计数子数组
int count_subarray(int arr[], int n, int k){
   int mod[k];
   memset(mod, 0, sizeof(mod));
   int cumSum = 0;
   for (int i = 0; i < n; i++) {
      cumSum += arr[i];
      //取模得到正和
      mod[((cumSum % k) + k) % k]++;
   }
   int result = 0;
   for (int i = 0; i < k; i++)
      if (mod[i] > 1)
         result += (mod[i] * (mod[i] - 1)) / 2;
   result += mod[0];
   return result;
}
int main(){
   int arr[] = { 4, 5, 0, -2, -3, 1 };
   int k = 5;
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << count_subarray(arr, n, k) << endl;
   int arr1[] = { 4, 5, 0, -12, -23, 1 };
   nt k1 = 5;
   int n1 = sizeof(arr1) / sizeof(arr1[0]);
   cout << count_subarray(arr1, n1, k1) << endl;
   return 0;
}

输出结果

7
7