Contest: Division 1
Contest: Division 2
Setter: Smit mandavia
Tester: Xiuhan Wang
Editorialist: Taranpreet Singh
Modulo operator and Basic Combinatorics.
Given two integers N and P, suppose the maximum value of (((N \bmod i) \bmod j) \bmod k ) \bmod N be M where i, j, k \in [1, P], Find the number of ways to select i, j, k \in [1, P] such that (((N \bmod i) \bmod j) \bmod k ) \bmod N equals M.
SUPER QUICK EXPLANATION
- The maximum value of N \bmod x where x \in [1,N], if N is odd, is (N-1)/2 when x = (N+1)/2, and if N is even, is N/2-1 when x = N/2+1.
- We can achieve (((N \bmod i) \bmod j) \bmod k ) \bmod N = M in three ways. Let x = \lceil (N+1)/2 \rceil
- i = x and j,k > M.
- i > N, j = x and k > M.
i, j > N and k = x.
Each of this case can be easily computed.
First of all, Let is find this value M. It has to be less than min(i,j,k,N) which implies, M < N. Hence, if we want M > 0, we need (((N \bmod i) \bmod j) \bmod k) < N. So, We know for sure, that to maximize M, min(i, j, k) \leq N. Hence, we need maximum (((N \bmod i) \bmod j) \bmod k) < N and now we can ignore the last \bmod N.
So, The maximum N \bmod x can attain is \lfloor (N-1)/2 \rfloor. This happens when x = \lceil (N+1)/2 \rceil. It can be easily verified either by checking by hand, or writing a simple program
Now, try finding out number of ways (((N \bmod i) \bmod j) \bmod k) equals M. It can be approached in Simple case base analysis.
We can try all possible triplets of (i,j,k) and generalize them into three cases.
- When i = \lceil (N+1)/2 \rceil and j,k > M
- When i > N, j = \lceil (N+1)/2 \rceil and k > M
- When i,j > N and k = \lceil (N+1)/2 \rceil
In all three cases, we can simply count the number of triplets (i, j, k) satisfying any condition and print the answer.
When N \leq 2, M = \lfloor (N-1)/2 \rfloor = 0. This is because we cannot achieve (((N \bmod i) \bmod j) \bmod k ) \bmod N > 0. So, all triplets (i, j, k) are valid.
Alternate solution - read at your own risk, you have been warned
For those curious enough not to be satisfied with such solutions, there also exists a pattern based solution too, using basic math. Just use brute solution to find the first terms of series and solve using the pattern formed. Number 6 is important. Enjoy
Time complexity is O(1) per test case.
AUTHOR’S AND TESTER’S SOLUTIONS:
Feel free to Share your approach, If it differs. Suggestions are always welcomed.