PROBLEM LINK:Practice Setter: Smit mandavia 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
EXPLANATIONFirst 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.
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 :D 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 :D Time ComplexityTime complexity is $O(1)$ per test case. AUTHOR'S AND TESTER'S SOLUTIONS:Setter's solution Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)
This question is marked "community wiki".
asked 14 Jan, 15:59

link
This answer is marked "community wiki".
answered 17 Jan, 21:19
