Binary exponentiation (also known as exponentiation by squaring) is a trick which allows to calculate $a^n$ using only $O(\log n)$ multiplications (instead of $O(n)$ multiplications required by the naive approach).

Luckily this is very easy, since an element in the sequence is just the square of the previous element.

$$\begin{align}

The following recursive approach expresses the same idea:

$$a^n = \begin{cases}

}

Given two non-negative integers $a$ and $b$, we have to find their **GCD** (greatest common divisor), i.e. the largest number which is a divisor of both $a$ and $b$.

It's commonly denoted by $\gcd(a, b)$. Mathematically it is defined as:

(here the symbol "$\mid$" denotes divisibility, i.e. "$k \mid a$" means "$k$ divides $a$")

When one of the numbers is zero, while the other is non-zero, their greatest common divisor, by definition, is the second number. When both numbers are zero, their greatest common divisor is undefined (it can be any arbitrarily large number), but we can define it to be zero. Which gives us a simple rule: if one of the numbers is zero, the greatest common divisor is the other number.

The algorithm is extremely simple:

While the [Euclidean algorithm](euclid-algorithm.md) calculates only the greatest common divisor (GCD) of two integers $a$ and $b$, the extended version also finds a way to represent GCD in terms of $a$ and $b$, i.e. coefficients $x$ and $y$ for which:

We found the values of $x$ and $y$:

$$\begin{cases}

int gcd(int a, int b, int& x, int& y) {

if (b == 0) {

x = 1;

In this article we will discuss an algorithm that allows us to multiply two polynomials of length $n$ in $O(n \log n)$ time, which is better than the trivial multiplication which takes $O(n^2)$ time.

The Fibonacci sequence is defined as follows:

Fibonacci numbers possess a lot of interesting properties. Here are a few of them:

* Cassini's identity:

* The "addition" rule:

* Applying the previous identity to the case $k = n$, we get:

* From this we can prove by induction that for any positive integer $k$, $F_{nk}$ is multiple of $F_n$.

* The inverse is also true: if $F_m$ is multiple of $F_n$, then $m$ is multiple of $n$.

* GCD identity:

* Fibonacci numbers are the worst possible inputs for Euclidean algorithm (see Lame's theorem in [Euclidean algorithm](euclid-algorithm.md))

Notice that this is the only occurrence where two consecutive 1-bits appear.

$$\begin{eqnarray}

Using above method we can find these equations:

$$ \begin{array}{rll}

Thus using above two equations Fibonacci numbers can be calculated easily by the following code:

A Linear Diophantine Equation (in two variables) is an equation of the general form:

Therefore one of the solutions of the Diophantine equation is:

The above idea still works when $a$ or $b$ or both of them are negative. We only need to change the sign of $x_0$ and $y_0$ when necessary.

Finally, we can implement this idea as follows (note that this code does not consider the case $a = b = 0$):

int gcd(int a, int b, int& x, int& y) {

if (b == 0) {

x = 1;

Once we have $l_x$ and $r_x$, it is also simple to enumerate through all the solutions. Just need to iterate through $x = l_x + k \cdot \frac{b}{g}$ for all $k \ge 0$ until $x = r_x$, and find the corresponding $y$ values using the equation $a x + b y = c$.

Here, $x$ and $y$ also need to be given some restriction, otherwise, the answer may become negative infinity.

Finally, use the knowledge of the set of all solutions to find the minimum:

Note that $x + y$ change as follows: