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

1514C - Product 1 Modulo N

 1514C - Product 1 Modulo N

Link : https://codeforces.com/problemset/problem/1514/C

Problem statement

We are given a number $n$, for which we want to find the maximum count of numbers which are less than this $n$, and have the modulo of their product as 1.

Solution

Here, the crux of the solution is this math stack exchange's post : https://math.stackexchange.com/questions/441667 

The critical point being:

Let $1 \leq b_1 < b_2 <...< b_{\phi(n)} < n$ be integers relatively prime with n.Prove that 

$$B_n = b_1 b_2 ... b_{\phi(n)} \equiv \pm 1 \bmod n $$

This can be proven by seeing that there are two types of numbers amongst Bs. One, which have a partner number, such that their product is 1 modulo $n$.

Two, which don't have a partner, and their product to themselves (i.e their square) modulo $n$ is $1$. But we don't have two of them. Instead note that $$ (x \times (n - x) ) \text{%} n = (-x^2)\text{%} n = -1$$

So let's see what the product of these two types of numbers will be. The first one will only contribute to 1, but the 2nd ones will contribute -1 for each of them. 

So we just have to multiply the co-primes, and check whether their product modulo $n$ is 1. If not, it will be $n-1$. This means that we can remove the pair of the 2nd type $1, (n-1)$ from the co-primes list. This would decrease the pairs of the 2nd type by 1, and thus our product will become 1 again. 

Note that removing 1 wouldn't make any sense from the co-primes, so we can just remove $n-1$. 

My submission : https://codeforces.com/contest/1514/submission/181683452