1603/B - Moderate Modular Mode

 Moderate Modular Mode

Problem

Link to the problem : https://codeforces.com/problemset/problem/1603/B

Here, we basically are given two numbers $x$ and $y$, and we need to find a number $n$ such that:

$$ n \text{%} x = y \text{%} n$$

$x$ and $y$ are pretty big numbers (~$2 \times 10 ^{18}$)

Solution

Let's divide the conditions. 

1. y < x

Case a) n < y < x

In this case $n \text{%} x = n$ and $y \text{%} n < n$. So these can never be equal and this case will never be true

Case b) y < n < x

In this case $n \text{%} x = n$ and $y \text{%} n = y$, and these will not be equal, so this case will also not be true

Case c) y < x < n

In this case $n \text{%} < x$ and $y \text{%} n = y$. This can be true. Note that a simple solve for this is $n = x + y$

This is what we can use in this case.

2. x = y

In this case we can simply put $n = x$, so both LHS and RHS will be zero.

3. x < y

This case can be divided into two more cases.

Case a) x doesn't divide y

So let's think about a multiple of $x$ that is nearest to $y$, and also less than $y$. That can be found by $\lfloor y / x \rfloor \times x$. Let's assume that value to be $k$.

Let's see the values between $k$ and $y$. The middle of those will not be divisible by $x$ (as the next multiple of $x$ will be more than $y$). Let's call this number $z$ (which is $(y + k)/2$).

Also note that this will not divide $y$ too. The maximum divisor of $y$ is $y/2$. $z$ is clearly more than that.

Now if we see the $ z \text{%} x$ we will find that it will be the delta between $z$ and $k$

Also $y \text{%} y$ will be be the delta between $z$ and $y$. Note that $z$ was in the middle of $k$ and $y$ so both these deltas will be equal. Therefore $z$ will be the answer, which is $ y/2 + \lfloor (y/x) \rfloor \times (x/2) $

Case b) x divides y

In this case $k$ will be equal to $y$. So a simple solution for this is to take the previous multiple of $x$. 

This will be equal to : $ x \times (\lfloor y / x \rfloor -1)$. We do the same calculation as in Case a.

The answer comes out to be $y - (x/2)$ in this case.

My submission : https://codeforces.com/contest/1603/submission/183138750