Числа Фібоначчі (Розбір)

Відомо, що для чисел Фібоначчі виконується рівність:

НОД (F_{n}, F_{m}) = F_{НОД (n, m)}

НОД(F_n, F_m) = F_{НОД(n,m)}

Це означає, що задача зводиться до обчислення $k$ -го числа Фібоначчі по модулю $1 0^{8}$ 10^8, де

k = НОД (n, m)

k = НОД(n, m)

Оскільки $n, m \leq 1 0^{18}$ n, m \le 10^{18}, то $k \leq 1 0^{18}$ k ≤ 10^{18}. Отже, необхідно обчислити значення $F_{k} m o d 1 0^{8}$ F_k~mod~10^8 за час $O (l o g_{2} k)$ O(log_2k).

Теорема. Для швидкого обчислення чисел Фібоначчі зручно використовувати матричне піднесення до степеня. Відомо, що:

(1110)^{k} = (F_{k + 1} F_{k} F_{k} F_{k - 1})

\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^k = \begin{pmatrix} F_{k+1} & F_k \\ F_k & F_{k-1} \end{pmatrix}

База індукції. При $k = 1$ k = 1 маємо:

(1110) = (F_{2} F_{1} F_{1} F_{0})

\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} F_2 & F_1 \\ F_1 & F_0 \end{pmatrix}

що правильно, оскільки $F_{0} = 0, F_{1} = 1, F_{2} = 1$ F_0 = 0, F_1 = 1, F_2 = 1.

Крок індукції. Припустимо, що формула правильна для $k$ . Тоді для $k + 1$ k + 1:

(1110)^{k + 1} = (F_{k + 1} F_{k} F_{k} F_{k - 1}) (1110) = (F_{k + 1} + F_{k} F_{k} + F_{k - 1} F_{k + 1} F_{k}) = (F_{k + 2} F_{k + 1} F_{k + 1} F_{k})

\begin{pmatrix}1 & 1 \\ 1 & 0\end{pmatrix}^{k+1} = \begin{pmatrix}F_{k+1} & F_k \\ F_k & F_{k-1}\end{pmatrix} \begin{pmatrix}1 & 1 \\ 1 & 0\end{pmatrix} = \begin{pmatrix}F_{k+1}+F_k & F_{k+1} \\ F_k+F_{k-1} & F_k\end{pmatrix} = \begin{pmatrix}F_{k+2} & F_{k+1} \\ F_{k+1} & F_k\end{pmatrix}

Таким чином, формула правильна для всіх $k \geq 1$ k \ge 1.

Залишилось реалізувати піднесення матриці до степеня $k$ з використанням швидкого піднесення до степеня за час $O (l o g_{2} k)$ O(log_2k).

Приклад

Числа Фібоначчі мають вигляд:

Обчислимо числа Фібоначчі за допомогою піднесення до степеня матриці:

(1110)^{2} = (1110) \cdot (1110) = (2111) = (F_{3} F_{2} F_{2} F_{1})

\begin{pmatrix}1 & 1 \\ 1 & 0\end{pmatrix}^2 = \begin{pmatrix}1 & 1 \\ 1 & 0\end{pmatrix} \cdot \begin{pmatrix}1 & 1 \\ 1 & 0\end{pmatrix} = \begin{pmatrix}2 & 1 \\ 1 & 1\end{pmatrix} = \begin{pmatrix}F_3 & F_2 \\ F_2 & F_1\end{pmatrix}

(1110)^{4} = (2111)^{2} = (2111) \cdot (2111) = (5332) = (F_{5} F_{4} F_{4} F_{3})

\begin{pmatrix}1 & 1 \\ 1 & 0\end{pmatrix}^4 = \begin{pmatrix}2 & 1 \\ 1 & 1\end{pmatrix}^2 = \begin{pmatrix}2 & 1 \\ 1 & 1\end{pmatrix} \cdot \begin{pmatrix}2 & 1 \\ 1 & 1\end{pmatrix} = \begin{pmatrix}5 & 3 \\ 3 & 2\end{pmatrix} = \begin{pmatrix}F_5 & F_4 \\ F_4 & F_3\end{pmatrix}

(1110)^{8} = (5332)^{2} = (5332) \cdot (5332) = (34212113) = (F_{9} F_{8} F_{8} F_{7})

\begin{pmatrix}1 & 1 \\ 1 & 0\end{pmatrix}^8 = \begin{pmatrix}5 & 3 \\ 3 & 2\end{pmatrix}^2 = \begin{pmatrix}5 & 3 \\ 3 & 2\end{pmatrix} \cdot \begin{pmatrix}5 & 3 \\ 3 & 2\end{pmatrix} = \begin{pmatrix}34 & 21 \\ 21 & 13\end{pmatrix} = \begin{pmatrix}F_9 & F_8 \\ F_8 & F_7\end{pmatrix}

Реалізація алгоритму – перевантаження операторів

Оголосимо константу $M O D$ , по модулю якої будуть проводитись обчислення.

#define MOD 100000000

Функція gcd обчислює найбільший спільний дільник двох чисел $a$ і $b$ .

long long gcd(long long a, long long b)
{
  return (!b) ? a : gcd(b, a % b);
}

Оголосимо клас матриці Matrix і опишемо конструктор.

class Matrix
{
public:
  long long a, b, c, d;
  Matrix(long long a = 1, long long b = 0, 
         long long c = 0, long long d = 1) 
  {
    this->a = a; this->b = b;
    this->c = c; this->d = d;
  }

C++

Перевантажимо оператор множення матриць. Всі обчислення виконуються по модулю $M O D = 1 0^{8}$ MOD = 10^8.

  Matrix operator* (const Matrix &x)
  {
    Matrix res;
    res.a = (a * x.a + b * x.c) % MOD;
    res.b = (a * x.b + b * x.d) % MOD;
    res.c = (c * x.a + d * x.c) % MOD;
    res.d = (c * x.b + d * x.d) % MOD;
    return res;
  }

C++

Перевантажимо оператор піднесення матриці до степеня $n$ . Часова складність алгоритму складає $O (l o g_{2} n)$ O(log_2n).

  Matrix operator^ (long long n)
  {
    Matrix x(*this);
    if (n == 0) return Matrix();
    if (n & 1) return x * (x ^ (n - 1));
    return (x * x) ^ (n/2);
  }
};

C++

Функція fib повертає $n$ -е число Фібоначчі $F_{n}$ F_n по модулю $1 0^{8}$ 10^8.

long long fib(long long n)
{
  Matrix res(1,1,1,0);
  res = res ^ n;
  return res.b;
}

Основна частина програми. Читаємо вхідні дані, обчислюємо та виводимо значення $F_{НОД (n, m)}$ F_{НОД(n, m)}.

while(scanf("%lld %lld",&n,&m) == 2)
{
  d = gcd(n,m);
  printf("%lld\n",fib(d));
}

Реалізація алгоритму – функції

Оголосимо константу $M O D$ , по модулю якої будуть проводитись обчислення.

#define MOD 100000000

Функція gcd обчислює найбільший спільний дільник двох чисел $a$ і $b$ .

long long gcd(long long a, long long b)
{
  return (!b) ? a : gcd(b, a % b);
}

Оголосимо структуру Matrix — матрицю розміру $2 \times 2$ 2 \times 2. За замовчуванням створюється одинична матриця, що зручно при піднесенні до степеня.

struct Matrix 
{
  long long a, b, c, d;
  Matrix(long long a_ = 1, long long b_ = 0,
         long long c_ = 0, long long d_ = 1)
         : a(a_), b(b_), c(c_), d(d_) {}
};

C++

Функція multiply перемножує дві матриці $2 \times 2$ 2 \times 2 за стандартною формулою.

Matrix multiply(Matrix &x, Matrix &y) 
{
  return Matrix(
    (x.a * y.a + x.b * y.c) % MOD,
    (x.a * y.b + x.b * y.d) % MOD,
    (x.c * y.a + x.d * y.c) % MOD,
    (x.c * y.b + x.d * y.d) % MOD
  );
}

C++

Функція power реалізує бінарне піднесення матриці $ba se$ до степеня $e x p$ .

Matrix power(Matrix base, long long exp) 
{
  Matrix result;
  while (exp > 0)
  {
    if (exp & 1)
      result = multiply(result, base);
    base = multiply(base, base);
    exp >>= 1;
  }
  return result;
}

C++

Функція fib обчислює $n$ -е число Фібоначчі по модулю $1 0^{8}$ 10^8 з використанням матричного методу.

long long fib(long long n) 
{
  if (n == 0) return 0;
  Matrix m(1, 1, 1, 0);
  Matrix res = power(m, n);
  return res.b; // F(n)
}

C++

Основна частина програми. Читаємо вхідні дані, обчислюємо та виводимо значення $F_{НОД (n, m)}$ F_{НОД(n, m)}.

while (scanf("%lld %lld", &n, &m) == 2) 
{
  d = gcd(n, m);
  printf("%lld\n", fib(d));
}

Реалізація алгоритму – запам'ятовування

Для чисел Фібоначчі відоме наступне тотожність:

F_{n + m} = F_{m} \cdot F_{n + 1} + F_{m - 1} \cdot F_{n}

F_{n+m} = F_m \cdot F_{n+1} + F_{m-1} \cdot F_n

З нього безпосередньо випливають часткові випадки:

якщо $m = n$ m = n, то $F_{2 n} = F_{n} \cdot F_{n + 1} + F_{n - 1} \cdot F_{n}$ F_{2n} = F_n \cdot F_{n+1} + F_{n-1} \cdot F_n.
якщо $m = n + 1$ m = n + 1, то $F_{2 n + 1} = F_{n + 1} \cdot F_{n + 1} + F_{n} \cdot F_{n}$ F_{2n+1} = F_{n+1} \cdot F_{n+1} + F_n \cdot F_n.

Ці формули дозволяють обчислювати числа Фібоначчі методом "розділяй і володарюй", зводячи обчислення $F_{n}$ F_n до значень з приблизно вдвічі меншими індексами.

Окремо обробляються базові випадки:

F_{0} = 0, F_{1} = F_{2} = 1

F_0 = 0, F_1 = F_2 = 1

Завдяки такому підходу глибина рекурсії пропорційна $l o g_{2} n$ log_2n, а часова складність алгоритму складає $O (l o g_{2} n)$ O(log_2n).

Оголосимо константу $M O D$ , по модулю якої будуть проводитись обчислення.

#define MOD 100000000

Оголосимо змінну $F$ типу map для запам'ятовування вже обчислених чисел Фібоначчі.

map<long long, long long> F;

Функція gcd обчислює найбільший спільний дільник двох чисел $a$ і $b$ .

long long gcd(long long a, long long b)
{
  return (!b) ? a : gcd(b,a % b);
}

Функція fib обчислює $n$ -е число Фібоначчі по модулю $1 0^{8}$ 10^8.

long long fib(long long n)
{

Окремо обробляємо базові випадки.

  if (n == 0) return 0;
  if (n == 1) return 1;
  if (n == 2) return 1;

Якщо значення $F_{n}$ F_n вже було обчислено раніше і збережено в $F$ , воно повертається одразу, без повторних обчислень.

  if (F[n]) return F[n];

Далі використовуємо розклад числа $n$ на:

$n = 2 k + 1$ n = 2k + 1 — непарний випадок: $F_{n} = F_{k}^{2} + F_{k + 1}^{2}$ F_n=F_k^2 + F_{k+1}^2.
$n = 2 k$ n = 2k — парний випадок: $F_{n} = F_{k} \cdot F_{k + 1} + F_{k - 1} \cdot F_{k}$ F_n = F_k \cdot F_{k+1} + F_{k-1} \cdot F_k.

  long long k = n / 2;

Зберігаємо та повертаємо результат.

  if (n % 2 == 1) // n = 2*k + 1
    return F[n] = (fib(k) * fib(k) + fib(k+1) * fib(k+1)) % MOD;
  else // n = 2*k
    return F[n] = (fib(k) * fib(k+1) + fib(k-1) * fib(k)) % MOD;
}

Основна частина програми. Читаємо вхідні дані, обчислюємо та виводимо значення $F_{НОД (n, m)}$ F_{НОД(n, m)}.

while(scanf("%lld %lld",&a,&b) == 2)
{
  d = gcd(a,b);
  printf("%lld\n",fib(d));
}

Java реалізація

import java.util.*;

public class Main
{
  static HashMap<Long, Long> F = new HashMap<Long, Long>();
  static long MOD = 100000000;
  
  static long gcd(long a, long b)
  {
    return (b == 0) ? a : gcd(b,a % b);
  }

  static long fib(long n)
  {
    if (n == 0) return 0;
    if (n == 1) return 1;
    if (n == 2) return 1;
    if (F.containsKey(n)) return F.get(n);

    long k = n / 2;
    if (n % 2 == 1)
    {
      F.put(n, (fib(k) * fib(k) + fib(k+1) * fib(k+1)) % MOD);
      return F.get(n);
    }
    else
    {
      F.put(n, (fib(k) * fib(k+1) + fib(k-1) * fib(k)) % MOD);    	
      return F.get(n);
    }
  }
  
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    while(con.hasNext())
    {
      long a = con.nextLong();
      long b = con.nextLong();
      long d = gcd(a,b);
      System.out.println(fib(d));  
    }
    con.close();
  }
}

Java