题目描述 给你一个长度为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 思路； (a+b)%k=((a%k)+(b%k))%k，两个数的和对k取余等于各自对k取余之后的和再对k取余，且取余之后的数都小于k。将每个数对k取余之后分类，余数相同的归到同一数组中，用余数作为数组的下标数，方便计算余数和取余时查找。
#include<iostream> #include<algorithm> #include<stdio.h> using namespace std; int main() { int n, k; cin >> n >> k; int x; int *b = new int[1000000]();//存放余数 for (int i = 0; i < n; i++) { scanf("%d", &x; b[x % k]++; } long long num = 0;//满足条件的数对个数 int i = 0, j; for (i = 0; i < k; i++) { j = (k - i) % k; if (i < j)//两个不同组 num += b[i] * b[j]; else if (i == j)//两个同组 num += (b[i] * (b[j] - 1)) / 2; else break;//后半部分与之前的重复 } cout << num << endl; delete[] b; return 0; }ps:
这里因为数组开的太大了，所以采用了动态分配内存的方法最后的结果共由两部分组成，不同组的余数和以及同组的余数和当两个同组余数组合可以得到k的倍数时，用排列组合的算法得到个数Cn2