[UVA] 11087 - Divisibility Testing
|
I I U P C 2 0 0 6 |
|
|
Problem D: Divisibility Testing |
|
|
Input: standard input |
|
|
|
|
|
You will be given a list of n integers, <a1 a2 a3 . . . an> and an integer k. Find out the number of ways of choosing 2 integers (ai, aj), such that ai ≤ aj and 1 ≤ i, j ≤ n and i ≠ j and (ai + aj) is divisible by k. Every pair must be distinct. Two pairs, (a, b) and (c, d), are equal if a is equal to c and b is equal to d.
Suppose we are given 5 integers <4 1 2 2 3> and k = 1. There are 7 ways of choosing different pairs that meets the above restrictions. (1, 2) (1, 3) (1, 4) (2, 2) (2, 3) (2, 4) (3, 4).
|
|
|
Input |
|
|
The first line of input contains an integer T that determines the number of test cases. Each test case contains two lines. The first line consists of two integers n and k. The next line contains n integers. The i-th integer gives the value of ai.
|
|
|
Output |
|
|
For each test case, output the case number followed by the number of ways to choose the pairs.
|
|
|
Constraints |
|
|
- T < 100
|
|
|
Sample Input |
Output for Sample Input |
|
2 |
Case 1: 7 |
|
|
|
|
Problemsetter: Sohel Hafiz |
|
sort 過一次，相同的就特別判斷。
由於 k < 501, 特別判斷。
然後直接在 cnt[] 計數即可。
#include <stdio.h>
#include <algorithm>
using namespace std;
int t, n, k, cases = 0;
int A[100005], B[100005];
void RadixSort(int *A, int *B, int n) {
int a, x, d, *T, C[256];
for(x = 0; x < 4; x++) {
d = x*8;
for(a = 0; a < 256; a++) C[a] = 0;
for(a = 0; a < n; a++) C[(A[a]>>d)&255]++;
for(a = 1; a < 256; a++) C[a] += C[a-1];
for(a = n-1; a >= 0; a--) B[--C[(A[a]>>d)&255]] = A[a];
T = A, A = B, B = T;
}
}
int main() {
scanf("%d", &t);
int i, j, k;
while(t--) {
scanf("%d %d", &n, &k);
for(i = 0; i < n; i++)
scanf("%d", &A[i]);
//ReadInt(&A[i]);
//sort(A, A+n);
RadixSort(A, B, n);
long long ans = 0;
if(n > 1 && A[0] == A[1] && (A[0]+A[1])%k == 0)
ans++;
for(i = 1, j = 0; i < n; i++) {
if(A[i] != A[j]) {
if(i+1 < n && A[i] == A[i+1] && (A[i]+A[i+1])%k == 0)
ans++;
A[++j] = A[i];
}
}
n = j+1;
int cnt[505] = {};
for(i = 0; i < n; i++) {
j = A[i]%k;
if(j < 0) j += k;
if(j)
ans += cnt[k-j];
else
ans += cnt[0];
cnt[j]++;
}
printf("Case %d: %d\n", ++cases, ans);
}
return 0;
}