数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中求数组中和能被 K 整除的数对个数
给定一个整数类型的数组，任务是从给定数组中形成数对，计算数对中元素的和，并检查给定的和是否能被 k 整除。
输入 − int arr[] = {4, 1, 2, 0, 2}, int k = 2
输出 − 数组中和能被 k 整除的数对个数为 − 2
解释 − 从给定数组中可以形成的数对为：(4, 1) = 5（不能被 2 整除），(4, 2) = 6（能被 2 整除），(4, 0) = 4（能被 2 整除），(1, 2) = 3（不能被 2 整除），(1, 0) = 1（不能被 2 整除），(2, 0) = 2（能被 2 整除），(2, 2) = 4（能被 2 整除），(0, 2) = 2（能被 2 整除）。因此，和能被 k（2）整除的数对为 (4, 2)，(4, 0)，(2, 0)，(2, 2) 和 (0, 2)。
输入 − int arr[] = {2, 4, 8, 6, 10} , int k = 4
输出 − 数组中和能被 k 整除的数对个数为 − 4
解释 − 从给定数组中可以形成的数对为：(2, 4) = 6（不能被 4 整除），(2, 8) = 10（不能被 4 整除），(2, 6) = 8（能被 4 整除），(2, 10) = 12（能被 4 整除），(4, 8) = 12（能被 4 整除），(4, 6) = 10（不能被 4 整除），(4, 10) = 14（不能被 4 整除），(8, 6) = 14（不能被 4 整除），(8, 10) = 18（不能被 4 整除），(6, 10) = 16（能被 4 整除）。因此，和能被 4 整除的数对为 (2, 10)，(2, 6)，(4, 8) 和 (6, 10)。
下面程序中使用的解决方法如下
解决给定问题的方法可能有多种，例如朴素方法和高效方法。所以让我们先看看朴素方法。
输入一个整数元素数组和一个整数变量 k，然后计算数组的大小并将数据传递给函数
声明一个临时变量 count 来存储和能被 k 整除的数对的个数。
从 i 为 0 开始，循环到数组大小
在循环内部，从 j 为 i + 1 开始，循环到数组大小
在循环内部计算和为 arr[i] + arr[j]，并检查 IF sum % k == 0，则将 count 加 1。
返回 count
打印结果。
高效方法
输入一个整数元素数组并计算数组的大小，并将数据传递给函数
声明一个临时变量 count 来存储和能被 k 整除的数对的个数。
创建一个大小为 k 的数组，因为我们需要检查是否能被 k 整除。
从 i 为 0 开始，循环到数组大小
在循环内部，将 temp 设置为 arr[i] % k，并将数组前置递增为 ++check[temp]
将 count 设置为 new_arr[0] * (new_arr[0] - 1)/2
从 i 为 1 开始，循环到 i <= k/2 且 i != (k-i)
在循环内部，将 count 设置为 count + new_arr[i] * (new_arr[k - i])
检查 IF k % 2 = 0，则将 count 设置为 count + (new_arr[k / 2] * (new_arr[k / 2] - 1) / 2)
返回 count
打印结果。
示例（朴素方法）
#include <iostream>
using namespace std;
int pair_k(int arr[], int size, int k){
int count = 0;
for(int i = 0 ;i <size ; i++){
for(int j = i+1; j<size; j++){
int sum = arr[i] + arr[j];
if(sum % k == 0){
count++;
}
}
}
return count;
}
int main(){
int arr[] = {4, 1, 2, 0, 2};
int size = sizeof(arr) / sizeof(arr[0]);
int k = 2;
cout<<"Count pairs in array whose sum is divisible by 4 are: "<<pair_k(arr, size, k);
return 0;
}输出
如果我们运行以上代码，它将生成以下输出：
Count pairs in array whose sum is divisible by k are: 6
示例（高效方法）
#include <iostream>
using namespace std;
int pair_k(int arr[], int size, int k){
int temp = 0;
int count = 0;
int check[k] = {0};
for (int i = 0; i < size; i++){
temp = arr[i] % k;
++check[temp];
}
count = check[0] * (check[0] - 1) / 2;
for (int i = 1; i <= k / 2 && i != (k - i); i++){
count = count + check[i] * (check[k - i]);
}
if (k % 2 == 0){
count = count + (check[k / 2] * (check[k / 2] - 1) / 2);
}
return count;
}
int main(){
int arr[] = {4, 1, 2, 0, 2};
int size = sizeof(arr) / sizeof(arr[0]);
int k = 2;
cout<<"Count pairs in array whose sum is divisible by 4 are: "<<pair_k(arr, size, k);
return 0;
}输出
如果我们运行以上代码，它将生成以下输出：
Count pairs in array whose sum is divisible by k are: 6
2K+ 次浏览
