PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Smit mandavia
Tester: Xiuhan Wang
Editorialist: Taranpreet Singh
DIFFICULTY:
Easy
PREREQUISITES:
Modulo operator and Basic Combinatorics.
PROBLEM:
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 (N1)/2 when x = (N+1)/2, and if N is even, is N/21 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.
EXPLANATION
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 (N1)/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.
Corner Case
When N \leq 2, M = \lfloor (N1)/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
Time complexity is O(1) per test case.
AUTHORâ€™S AND TESTERâ€™S SOLUTIONS:
Setterâ€™s solution
Testerâ€™s solution
Editorialistâ€™s solution
Feel free to Share your approach, If it differs. Suggestions are always welcomed.