PROBLEM LINKS
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.