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:

// 0-based implementation
template<typename T>
T extended_euclidean(const deque<T> &cof, deque<T> &var) {
	int n = cof.size();
	if (!cof.back()) {
		int cnt = 0, id = 0;
		for (int i = 0; i < n; i++)
			if (!cof[i]) {
				cnt++;
				var[i] = 0;
			} else
				id = i;
		if (cnt >= n - 1) {
			var[id] = 1;
			return cof[id];
		}
		deque<T> new_cof, new_var;
		for (int i = 0; i < n; i++)
			if (cof[i]) {
				new_cof.push_back(cof[i]);
				new_var.push_back(var[i]);
			}
		T g = extended_euclidean(new_cof, new_var);
		for (int i = 0; !new_var.empty(); i++)
			if (cof[i]) {
				var[i] = new_var.front();
				new_var.pop_front();
			}
		return g;
	}
	deque<T> new_cof = cof;
	for (int i = 0; i < n - 1; i++)
		new_cof[i] %= new_cof.back();
	new_cof.push_front(new_cof.back());
	new_cof.pop_back();
	var.push_front(var.back());
	var.pop_back();
	T g = extended_euclidean(new_cof, var);
	var.push_back(var.front());
	var.pop_front();
	for (int i = 0; i < n - 1; i++)
		var.back() -= cof[i] / cof.back() * var[i];
	return g;
}
template<typename T>
vector<T> find_any_solution(const vector<T> &cof, T rhs) {
	int n = cof.size();
	if (!n)
		return vector<T>();
	deque<T> deque_cof(cof.begin(), cof.end()), deque_var(n);
	T g = extended_euclidean(deque_cof, deque_var);
	if (g && rhs % g)
		return vector<T>();
	vector<T> var(deque_var.begin(), deque_var.end());
	if (g) {
		rhs /= g;
		for (auto &it : var)
			it *= rhs;
	}
	return var;
}