### Ahmed-Yasser's blog

By Ahmed-Yasser, 3 years ago,

I was learning the extended Euclidean algorithm in basic number theory and wondered how I should solve it for $n$ variables without using the fact that $gcd(cof_1,cof_2,\ldots,cof_n) = gcd(cof_1,gcd(cof_2,cof_3,\ldots,cof_n))$ as this can get overflow in specific test cases.

## Concept

I tried to grasp the idea of extended Euclidean for $2$ variables. It used the fact that $gcd(a + b, b) = gcd(a, b) = gcd((a + b) \bmod b, b)$ such that $a > 0$ and $b > 0$. This fact can be easily applied to $n$ variables by taking $\bmod cof_n$ to all the $n - 1$ coefficients from $1$ to $n - 1$ and moving the last element to the beginning, aka right cyclic shift, since $cof_n$ is now greater than all other coefficients and taking another modulo will change nothing.

The extended Euclidean for $2$ variables also used the fact that $gcd(a,0)=a$ and to solve the equation $a \cdot x + b \cdot y = GCD$, $x$ must equal $1$ since $b$ equals $0$. Also, $x$ and $y$ for the previous call of the function can be deduced from the current call using $y_{prev} = x_{cur} - a_{prev} / b_{prev} \cdot y_{cur}$. This also can be generalized to $n$ variables as we always take $\bmod cof_n$, so the equation will be $var_{n,prev} = var_{1,cur} - \sum_{i=1}^{n - 1}cof_{i,prev} / cof_{n,prev} \cdot var_{i+1,cur}$ such that $cof_i$ stands for $coefficient_i$ and $var_i$ stands for $variable_i$.

The last thing to handle is the case where one of the coefficients became $0$. My idea for it is to just discard those coefficients and their corresponding variables (as their values will not change anymore) as long as there are at least $2$ non-zero coefficients. Otherwise, the $gcd$ is the value of that non-zero coefficient (or $0$ if there are no non-zero coefficients) and its corresponding $var$ should equal $1$.

## Implementation

For easy manipulations, I needed to use deque. In the implementation, the equation in the second paragraph of the Concept section is a little different. Since a right cyclic shift happens after taking $\bmod a_n$ and before each call, the $var$ deque is cyclically shifted too, so $var_{1, cur}$ is the same as the $var_{n, prev}$, and $var_{i+1,cur}$ is the same as the $var_{i,prev}$. As for the complexity, I tested this algorithm against the Fibonacci series and found that it takes an approximated memory and time complexity of $O(cof_{size} \cdot log(cof_{min}))$. This is my implementation:

Implementation
• +50

By Ahmed-Yasser, 4 years ago,

While I was trying to solve a problem with dijkistra, something strange happened. I got an MLE test 2, but I discovered that after I changed some lines, which are not supposed to cause an MLE, with the corresponding lines in an AC code , it got AC. I'm now stuck in trying to understand why that happened!

The problem

The MLE solution

The AC solution

The two codes are identical. I just commented the call of a function and called the other in main!

• +10