DIVPAIR - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

MEDIUM

EXPLANATION

The values of 1 to N modulo M are like this:

1 2 3 … (M-1) 0 1 2 3 … (M-1) 0 … N%M

There are x=floor(N/M) occurrences of the full cycle “1 2 3 … (M-1) 0” and a partial cycle up to the term y=N%M.

First consider the case when both a,b ( a,b from the problem description) are from a full cycle [ between 1 and x*M ] . For a particular value of a, the corresponding b [ (a+b)%M = 0] will exist as both numbers are taken from a full cycle.

So there are x * x *(M-1) ways to select a divisible pair when a!=0 and b!=0. [ as x full cycles and (M-1) nonzero values modulo M].

And x*(x-1) ways to select a pair where, a=b=0. [ x-1 because you have to select b from another full cycle otherwise it’s the same number as a]

Now look, when M is an even number some pairs with the same number was added.[ where a=b and a%M=M/2 and they are from the same full cycle].So subtract the count of those.

Now all pairs are calculated twice, we are only interested in the pairs where a < b , so divide by 2.

Now, consider the case when b is from the partial cycle part and a is between 1 and x * M. There are y * x ways to do that.

And finally when both a and b are from the partial cycle. In this case a should be in the range of 1 <=a < M/2 and there are y-M/2 available values for b. So in this case add y-M/2 to the count of the answer.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

3 Likes