Fibonacci ədədləri (Həll təhlili)

Məlumdur ki, Fibonacci ədədləri üçün aşağıdakı bərabərlik doğrudur:

e x t QO B (F_{n}, F_{m}) = F_{e x t QO B (n, m)}

ext{QOB}(F_n, F_m) = F_{ ext{QOB}(n,m)}

Bu o deməkdir ki, məsələnin həlli $1 0^{8}$ 10^8 modula uyğun $k$ -ci Fibonacci ədədinin hesablanmasına çevrilir, burada

k = e x t QO B (n, m)

k = ext{QOB}(n, m)

Çünki $n, m \leq 1 0^{18}$ n, m \le 10^{18}, buna görə də $k \leq 1 0^{18}$ k ≤ 10^{18}. Nəticədə, $F_{k} m o d 1 0^{8}$ F_k~mod~10^8 dəyərini $O (l o g_{2} k)$ O(log_2k) müddətində hesablamaq lazımdır.

Teorem. Fibonacci ədədlərini sürətlə hesablamaq üçün matris üsulundan istifadə etmək əlverişlidir. Məlumdur ki:

(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}

İnduksiya Bazası. $k = 1$ k = 1 üçün alırıq:

(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}

Bu doğrudur, çünki $F_{0} = 0, F_{1} = 1, F_{2} = 1$ F_0 = 0, F_1 = 1, F_2 = 1.

İnduksiya Addımı. Formulun $k$ üçün doğru olduğunu güman edək. O zaman $k + 1$ k + 1 üçün:

(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}

Nəticə etibarilə, formul bütün $k \geq 1$ k \ge 1 üçün doğrudur.

Yerdə qalır matrisin $k$ əmsalına sürətli yüksəltmə üsulu ilə $O (l o g_{2} k)$ O(log_2k) müddətində əmələ gətirilməsi.

Misal

Fibonacci ədədləri belə görünür:

Matris üsulu ilə Fibonacci ədədlərini hesablayacağıq:

(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}

Algoritmin təcəssümü – operatorların aşırı yüklenməsi

Hesablama işlərini modula $M O D$ ilə aparmaq üçün bir sabit təyin edək.

#define MOD 100000000

gcd funksiyası iki ədəd $a$ və $b$ arasında ən böyük ortaq dəyəri hesablayır.

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

Matrix matrisini elan edək və konstruktörünü təsvir edək.

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++

Matrislərin vurulması operatorunu aşırı yükleyək. Bütün hesablamaları $M O D = 1 0^{8}$ MOD = 10^8 modula uyğun aparırıq.

  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++

Matrisin $n$ dərəcəsinə yüksəlməsinə aşırı yüklenmə üsulunu tətbiq edək. Algoritmin iş müddəti $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 funksiyası $n$ -inci Fibonacci ədədini $F_{n}$ F_n $1 0^{8}$ 10^8 modula uyğun olaraq verir.

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

Programın əsas hissəsi. Giriş məlumatlarını oxuyuruq, sonra $F_{e x t QO B (n, m)}$ F_{ ext{QOB}(n, m)} dəyərini hesablamaq və çıxmaq.

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

Algoritmin təcəssümü – funksiyalar

Hesablama işlərini modula $M O D$ ilə aparmaq üçün bir sabit təyin edək.

#define MOD 100000000

gcd funksiyası iki ədəd $a$ və $b$ arasında ən böyük ortaq dəyəri hesablayır.

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

Matrix strukturunu elan edək – $2 \times 2$ 2 \times 2 ölçüsündə matris. Əks şərtlər üçün default olaraq vahid matris yaratılır, bu yüksəltmə zamanı əlverişlidir.

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 funksiyası standart formul ilə iki matris $2 \times 2$ 2 \times 2 vurur.

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 funksiyası matris $ba se$ -in $e x p$ əmsalına binar üsul ilə yüksəlməsini təmin edir.

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 funksiyası matris metodi ilə $n$ -ci Fibonacci ədədini $1 0^{8}$ 10^8 modula uyğun olaraq verir.

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++

Programın əsas hissəsi. Giriş məlumatlarını oxuyuruq, sonra $F_{e x t QO B (n, m)}$ F_{ ext{QOB}(n, m)} dəyərini hesablamaq və çıxmaq.

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

Algoritmin təcəssümü - xatırlatma

Fibonacci ədədləri üçün aşağıdakı bərabərlik məlumdur:

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

Bunlardan birbaşa olaraq xüsusi halları çıxarıla bilər:

$m = n$ m = n olduqda, $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 olduqda, $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.

Bu formullar Fibonacci ədədlərini "böl və idarə et" metodu ilə hesablamağa imkan verir, hesablama $F_{n}$ F_n dəyərini təxminən yarıya indirən indekslərə çox asan olur.

Baza halları ayrıcayrıca işlənir:

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

F_0 = 0, F_1 = F_2 = 1

Bu yanaşma sayəsində rekursiyanın dərinliyi $l o g_{2} n$ log_2n-dən proporsionaldır və algoritmin iş müddəti $O (l o g_{2} n)$ O(log_2n)-dir.

Hesablama işlərini modula $M O D$ ilə aparmaq üçün bir sabit təyin edək.

#define MOD 100000000

$F$ tipli dəyişənmap003e Fibonacci ədədlərini artıq hesablamaq üçün saxladırıq.

map<long long, long long> F;

gcd funksiyası iki ədəd $a$ və $b$ arasında ən böyük ortaq dəyəri hesablayır.

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

fib funksiyası $n$ -ci Fibonacci ədədini $1 0^{8}$ 10^8 modula uyğun olaraq verir.

long long fib(long long n)
{

Baza halları ayrıcayrıca işlənir.

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

Əgər $F_{n}$ F_n dəyəri artıq əvvəllər hesablanmış və $F$ -də saxlanmışsa, bu dəyər təkrar hesablama olmadan dərhal qaytarılır.

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

Daha sonra $n$ üzərində parçalanma:

$n = 2 k + 1$ n = 2k + 1 — tək hal: $F_{n} = F_{k}^{2} + F_{k + 1}^{2}$ F_n=F_k^2 + F_{k+1}^2.
$n = 2 k$ n = 2k — cüt hal: $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;

Sonucu saxlayıb qaytarırıq.

  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;
}

Programın əsas hissəsi. Giriş məlumatlarını oxuyuruq, sonra $F_{e x t QO B (n, m)}$ F_{ ext{QOB}(n, m)} dəyərini hesablamaq və çıxmaq.

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

Java təcəssümü

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