C - Ringo's Favorite Numbers 2 Editorial by en_translator


\(A_i - A_j\) is a multiple of \(200\)” if and only if “the remainder of \(A_i\) divided by \(200\) and that of \(A_j\) are the same”.

So, the desired answer is equal to the number of pairs \((i,j)\) \((1 \le i < j \le N)\) (that is, the number of choices of two elements with the different position) such that remainder of \(A_i\) divided by \(200\) and that of \(A_j\) are the same.

First, let us find how many elements are there in \(A_i\) whose remainder by \(200\) is \(k\). In this problem, counting with a naive loop is sufficient, but a packet-sort like inspection is faster.
Assume that the sequence \(A_i\) contains \(X\) elements whose remainders by \(200\) are \(k\). Then, the number of combinations of two distinct elements from the sequence \(A\) is \(\frac{X \times (X-1)}{2}\). This is also true for \(X=0,1\).
The problem can be solved by summing them up for every integer from \(0\) through \(199\), inclusive.

The total complexity is \(O(N)\).

Sample code in C:

#include<stdio.h>

int main(){
  int n,a[200005];
  long long b[200]={0};
  scanf("%d",&n);
  for(int i=0;i<n;i++){
    scanf("%d",&a[i]);
    b[a[i]%200]++;
  }
  long long res=0;
  for(int k=0;k<200;k++){
    res+=(b[k]*(b[k]-1))/2;
  }
  printf("%lld\n",res);
  return 0;
}

Appendix 1: About the equivalence

\(A_i - A_j\) is a multiple of \(200\)” if and only if “the remainder of \(A_i\) divided by \(200\) and that of \(A_j\) are the same”.

We will explain the reason.
If the remainders of some two elements \(A_i\) and \(A_j\) by \(200\) are equal, the difference between these two elements are only due to their quotients divided by \(200\). Moreover, their difference is always a multiple of \(200\).
Conversely, if the remainders of some two elements \(A_i\) and \(A_j\) by \(200\) are not equal, then \(A_i-A_j\) is a multiple of \(200\). This is because, no matter how many times we add or subtract \(200\) to/from \(A_j\), the remainder by \(200\) does not change, so it will never be equal to \(A_i\).

Appendix 2: About the number of combinations

Assume that the sequence \(A_i\) contains \(X\) elements whose remainders by \(200\) are \(k\). Then, the number of combinations of two distinct elements from the sequence \(A\) is \(\frac{X \times (X-1)}{2}\).

We will explain the reason.
Now, let us consider how many choices are there of two objects out of \(X\) pairwise distinguishable objects.
We first choose the first object. There are \(X\) choices. Here, no matter which object was chosen, there are \(X-1\) choice of the second object.
After all, the number of combinations is \(X \times (X-1)\). In this problem, you are asked to just choose two objects, and their order (there are two of them) is not distinguished. Therefore, the desired number of choices is \(\frac{X \times (X-1)}{2}\).

posted:
last update: