Extended Euclidean algorithm for n variables 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 th...

Full text and comments »

Algorithms repo on github Hi all! Several months ago I decided to write down all the algorithms I know (and don't know) in one Visual Studio project for reusing, remembering, preparing to the interviews and easy learning of new algorithms and compose them in the one big library. I have implemented some part of this library, but before going deeper I want to provide some examples of library current usages: <spoiler summary="Example"> For example, you can compute Fibonacci n-th element using matrix exponentiation by writing the following code: ~~~~~ #include <iostream> #include <Math/Math.h> using namespace std; int main() { algo::Matrix<int> mat{ {1, 1}, { 1, 0 } }; algo::Matrix<int> neutral{ {1, 0}, { 0, 1 } }; algo::Matrix<int> fib { {1, 1} }; mat = algo::bin_pow(mat, 7, neutral, algo::matrix_mul<int>); fib = algo::matrix_mul(fib, mat); cout << fib[0][0]; // prints 34 } ~~~~~ After this code compiles another file is generated that do not contain any of r...

Full text and comments »

AlgoThugs 2026 — Editorial ### Contest announcement blog: [Link](https://mirror.codeforces.com/blog/entry/152857) ### [problem:669000A] Author: [user:Krishnadev44,2026-04-15] <spoiler summary="Hint 1"> We claim that the answer is always `YES`. </spoiler> <spoiler summary="Hint 2"> Let the direct path from vertex $u$ to vertex $v$ consist of $d$ edges. Since $u$ and $v$ are distinct, $d \ge 1$. Let the sequence of costs along these edges be $C = (c_1, c_2, \dots, c_d)$. We claim that there always exists a contiguous subarray of $C$ whose sum is perfectly divisible by $d$. </spoiler> <spoiler summary="Solution"> Let $S$ denote the prefix sum array of $C$, where the $k$-th prefix sum is defined as: $$S_k = \sum_{i=1}^{k} c_i \quad \text{for } 1 \le k \le d$$ Consider the values of these prefix sums modulo $d$. There are two cases: * Case $1$: There exists an index $k$ such that $S_k \equiv 0 \pmod d$. In this case, the sum of the prefix subarray $(c_1, c_2, \dots, c_k)$ is directly divisi...

Full text and comments »

How to solve it using dp (Distinct Adjacent) ?  [Question](https://atcoder.jp/contests/abc307/tasks/abc307_e) #### I didn't understand the editorial please help

Full text and comments »