×

# MGAME - EDITORIAL

Setter: Smit mandavia
Tester: Xiuhan Wang
Editorialist: Taranpreet Singh

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 $(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.

# 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 (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.

Corner Case

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 :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 Complexity

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. :)

This question is marked "community wiki".

4.0k31104
accept rate: 22%

1.6k211

 2 About the alternate solution, since this contest has no restriction, one could reference OEIS and came up with something like this: #include #define sqr(x) ((x) * (x)) int main() { long long t, n, p, diff, u, v; scanf("%lld", &t); while(t--) { scanf("%lld %lld", &n, &p); if (n < 3) { printf("%lld\n", p * p * p); continue; } diff = p - n; if (diff % 2) { u = n / 2, v = diff/2; printf("%lld\n", (u+v*3+2)*(u+v*3+3) + v*(v+1)*3 + 1); } else { printf("%lld\n", sqr(p/2 + diff + 1) + sqr(diff)*3/4); } } return 0; }  answered 15 Jan, 09:28 3★mcsinyx 31●4 accept rate: 0% wow... nice solution :) (15 Jan, 13:11) I tried similar approach but failed to formulate it properly, can you share how you found patter in odd number greater than 3. (21 Jan, 16:00)
 0 #include #define int long long int using namespace std; int32_t main() { int t; cin>>t; while(t--) { int n,p; cin>>n>>p; if(n==1||n==2) cout<
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×3,820
×900
×728
×348
×112
×30