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:
