PROBLEM LINK:Author: Kevin Atienza DIFFICULTY:Simple PREREQUISITES:Greatest common divisors, Euclid's algorithm, Linear combinations, Bézout's identity PROBLEM:Alvin has $A$ candies and Berto has $B$ candies. You can give $C$ candies to Alvin at a time, and $D$ candies to Berto at a time. What is the minimum possible absolute difference between their candies that can be achieved? QUICK EXPLANATION:Let $G = \gcd(C,D)$. Then every possible absolute difference is of the form $A  B + kG$ for some integer $k$, and every difference of that form can be achieved. The lowest difference that can be achieved is $\min((A  B) \bmod G, (B  A) \bmod G)$. EXPLANATION:First, any absolute value is nonnegative, so the lowest possible answer in every test case is $0$. Sometimes, this can be achieved, like in the first sample input. But in some cases this cannot be achieved. For example, in the second sample input, $A = 1$ and $B = C = D = 2$. In this case, you can only increase $A$ and $B$ by an even amount, so you can't make them have the same parity. Here's another example. Suppose $A = 11$, $B = 35$, $C = 50$ and $D = 130$. Notice that $\gcd(C,D) = 10$. Thus, no matter what you do, you cannot change the last digit of $A$ and $B$. The difference between any pair of numbers whose last digits are $1$ and $5$ respectively ends in either $4$ or $6$. Thus, the lowest possible difference we can get is $4$, and it turns out we can achieve this difference by adding $C$ to $A$ three times and $D$ to $B$ one time: $(11 + 3\cdot 50)  (35 + 1\cdot 130) = 165  161 = 4$. We can generalize the insight we got from the previous example. Suppose we add $C$ to $A$ $m$ times and $D$ to $B$ $n$ times. Then the absolute difference that we get is $(A + mC)  (B + nD) = (A  B) + (mC  nD)$. Every number of the form $mC  nD$ (a linear combination) is divisible by $\gcd(C,D)$! Thus, we can state the following: If $G = \gcd(C,D)$, then every possible absolute difference is of the form $A  B + kG$ for some integer $k$. The smallest possible value of the form $A  B + kG$ depends on the sign of the number inside the absolute value. If it's possible, then the smallest you can get is $$(A  B + kG) \bmod G = (A  B)\bmod G,$$ and if it's negative, then it is $$(A  B + kG)\bmod G = (B  A)\bmod G.$$ (Remember that $x \bmod G$ is always nonnegative even if $x$ is negative.) Thus, the answer is at least $$\min((A  B)\bmod G, (B  A)\bmod G).$$ Unfortunately, we haven't yet proved that every integer of the form $A  B + kG$ can be achieved as a difference, so "$\min((A  B)\bmod G, (B  A)\bmod G)$" is just a lower bound at this point. Thus, we want to know whether the following is true: Let $G = \gcd(C,D)$. Can every possible value of the form $A  B + kG$ for any integer $k$ be expressed in the form $A  B + (mC  nD)$ for some nonnegative integers $m$ and $n$? If we can show this, then we establish that the answer is $\min((A  B)\bmod G, (B  A)\bmod G)$. If not, then we'll have to find other ways. Note that the word "nonnegative" is pretty important; Without it, then we can easily answer the problem by using Bézout's identity: If $G = \gcd(C,D)$, then there exist integers $x$ and $y$ such that $Cx + Dy = G$. Using this theorem, we can now achieve any difference $A  B + kG$ by setting $m = kx$ and $n = ky$. Unfortunately, the theorem doesn't guarantee anything about the signs of $x$ and $y$. But actually, there's a way to convert any choice $(m,n)$ to a new choice $(m',n')$ such that both are nonnegative, by noticing that if $(m,n)$ is a valid choice, then $(m+D,n+C)$ is also valid! It's simply because $$(m+D)C  (n+C)D = mC + DC  nD  CD = mC  nD.$$ But $m+D$ and $n+C$ are strictly greater than $m$ and $n$, respectively, so we can apply this rule over and over again until both $m$ and $n$ become positive! This last piece proves that the answer is $\min((A  B) \bmod G, (B  A) \bmod G)$. Another way to look at it is that we can (partially) strengthen Bézout's identity to the following two statements: 1. If $G = \gcd(C,D)$ and $C$ and $D$ are positive, then there exist integers $x > 0$ and $y < 0$ such that $Cx + Dy = G$. 2. If $G = \gcd(C,D)$ and $C$ and $D$ are positive, then there exist integers $x < 0$ and $y > 0$ such that $Cx + Dy = G$. The proof goes similarly: For any $(x,y)$ satisfying $Cx + Dy = G$, the pairs $(x + D, y  C)$ and $(x  D, y + C)$ also satisfies it, so we can keep on applying these until we get the signs that we want. And since we choose $(m,n) = (kx,ky)$, then:
Appendix: Bézout's identityHere we'll prove Bézout's identity: If $G = \gcd(C,D)$, then there exist integers $x$ and $y$ such that $Cx + Dy = G$. We will actually prove this constructively, that is, by giving an algorithm that finds such $x$ and $y$. Our solution here will involve Euclid's algorithm to compute GCD's. The basic Euclid recursion for GCD goes: Another way of looking at it is that we're generating a sequence of numbers $r_0, r_1, r_2, \ldots$ such that:
And we halt this sequence when $r_i$ becomes $0$, in which case $r_{i1}$ is the GCD! For example, suppose we want to find the GCD of $C = 602$ and $D = 427$. Then: $$\begin{array}{rrrrrr} i & & & & & r_i \\ \hline 0 & & & & & 602 \\ 1 & & & & & 427 \\ 2 & 602 &\bmod& 427 &=& 175 \\ 3 & 427 &\bmod& 175 &=& 77 \\ 4 & 175 &\bmod& 77 &=& 21 \\ 5 & 77 &\bmod& 21 &=& 14 \\ 6 & 21 &\bmod& 14 &=& 7 \\ 7 & 14 &\bmod& 7 &=& 0 \end{array}$$ Since $r_7 = 0$, we find that the GCD is $r_6$, or $7$. But notice that "$a\bmod b$" is equivalent to "$a  qb$", where $q = \lfloor a/b \rfloor$. Thus, every number is a linear combination of the numbers above it: $r_i = r_{i2}  qr_{i1}$, where $q = \left\lfloor \frac{r_{i2}}{r_{i1}} \right\rfloor$. By also noticing that $C$ and $D$ can be written as linear combinations of themselves: $C = C\cdot 1 + D\cdot 0$ and $D = C\cdot 0 + D\cdot 1$, we can express each subsequent value as a linear combination of $C$ and $D$ too, and by doing so we're able to extend Euclid's algorithm to actually find the coefficients $x$ and $y$! For example, using $C = 602$ and $D = 427$ again: $$\begin{array}{rrrrrrrrrrrr} i & \left\lfloor \frac{r_{i2}}{r_{i1}} \right\rfloor & & & & & r_i & & & & & \text{linear combination} \\ \hline 0 & & & & & & 602 & & & & & C\cdot 1 + D\cdot 0 \\ 1 & & & & & & 427 & & & & & C\cdot 0 + D\cdot 1 \\ 2 & 1 & 602 &{}1\,\cdot& 427 &=& 175 & (C\cdot 1 + D\cdot 0) &{}1\,\cdot& (C\cdot 0 + D\cdot 1) &=& C\cdot 1 + D\cdot 1 \\ 3 & 2 & 427 &{}2\,\cdot& 175 &=& 77 & (C\cdot 0 + D\cdot 1) &{}2\,\cdot& (C\cdot 1 + D\cdot 1) &=& C\cdot 2 + D\cdot 3 \\ 4 & 2 & 175 &{}2\,\cdot& 77 &=& 21 & (C\cdot 1 + D\cdot 1) &{}2\,\cdot& (C\cdot 2 + D\cdot 3) &=& C\cdot 5 + D\cdot 7 \\ 5 & 3 & 77 &{}3\,\cdot& 21 &=& 14 & (C\cdot 2 + D\cdot 3) &{}3\,\cdot& (C\cdot 5 + D\cdot 7) &=& C\cdot 17 + D\cdot 24 \\ 6 & 1 & 21 &{}1\,\cdot& 14 &=& 7 & (C\cdot 5 + D\cdot 7) &{}1\,\cdot& (C\cdot 17 + D\cdot 24) &=& C\cdot 22 + D\cdot 31 \\ 7 & 2 & 14 &{}2\,\cdot& 7 &=& 0 & (C\cdot 17 + D\cdot 24) &{}2\,\cdot& (C\cdot 22 + D\cdot 31) &=& C\cdot 61 + D\cdot 86 \end{array}$$ Thus, we establish that $\gcd(C,D) = 7$, and $C\cdot 22 + D\cdot 31 = 7$! It's easy to see that this method can also be applied for any pair $(C,D)$. This is one version of the extended Euclid's algorithm. Time Complexity:$O(\log \min(C, D))$ AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 03 Jun '16, 04:02

answered 05 Jun '16, 21:56

Hi,I didn't get this line ."If it's possible, then the smallest you can get is : (AB+kG) mod G". Please explain it. answered 07 Aug '17, 08:27

What if we also want to know the sequence in which the candies were given? How to print the sequence? answered 20 Jan '18, 19:47

@bhagirathi08 ,suppose that the initial apples and bananas be 0, then the difference that can be created is kg, but since initially they were a and b the difference which can be created is (AB+kg) k can also be negative answered 04 Sep '18, 17:08

how smallest value of (A−B+kG)=(A−B)modG? I didn't get it. Please explain answered 07 Oct '18, 11:04
