时间限制 1000 ms
内存限制 64 MB
题目描述
给你一个长度为n的数组和一个正整数k，问从数组中任选两个数使其和是k的倍数，有多少种选法
对于数组a1=1 , a2=2 , a3=2而言：
(a1,a2)和(a2,a1)被认为是同一种选法；
(a1,a2)和(a1,a3)被认为是不同的选法。
输入数据
第一行有两个正整数n，k。n<=1000000，k<=1000000 第二行有n个正整数，每个数的大小不超过1e9
输出数据
选出一对数使其和是k的倍数的选法个数
样例输入
5 6
1 2 3 4 5
样例输出
2
样例说明
样例解释：
a1+a5=6，a2+a4=6，都是6的倍数
所以符合条件的选法有（1，5），（2，4）
#include<stdio.h>
#include<math.h>
#include <iostream>
using namespace std;
int main(){
int k, n;
int *a, *b;
//int *a;
cin >> n >> k;
a = (int *)malloc(sizeof(int) * (n)); // 分配
b = (int *)malloc(sizeof(int) * (k)); // 分配
//int a[1000000] = { 0 };
//int b[1000000] = { 0 };
for (int i = 0; i<n; i++)
{
//cin >> a[i]; // 键盘输入 n 个数
scanf("%d", &a[i]);
}
int count = 0;
for (int i = 0; i<k; i++)
{
b[i] = 0;
}
for (int i = 0; i < n; i++)
{
int temp = a[i] % k;
b[temp] ++;
}
//int m = k / 2;
count = count + b[0] * (b[0] - 1) / 2;
if (k % 2 == 0){
for (int j = 1; j < k / 2; j++){
count = count + b[j] * b[k - j];
}
count = count + b[k / 2] * (b[k / 2] - 1) / 2;
}
else{
for (int j = 1; j <= k / 2; j++){
count = count + b[j] * b[k - j];
}
}
//cout << count << endl;
printf("%d\n", count);
return 0;
}
