Fibonaççi hərarəti (Həll təhlili)

$n$ ədədi $1 0^{18}$ 10^{18}-ə qədər ola bildiyindən Fibonaççi ədədlərini bir-bir hesablamaq mümkün deyil. Matris üsulu da yaramır: $k$ -cı qüvvətlərin cəmi üçün ölçüsü təxminən $k$ olan matris lazım olardı, $k$ isə $1 0^{5}$ 10^5-ə qədər ola bilər. Buna görə Fibonaççi ədədləri üçün açıq düsturdan — Bine düsturundan istifadə edək:

f_{i} = \frac{φ ^{i} - ψ ^{i}}{5},

f_i = \frac{\varphi^i - \psi^i}{\sqrt{5}},

burada

φ = \frac{1 + 5}{2}, ψ = \frac{1 - 5}{2}

\varphi = \frac{1 + \sqrt{5}}{2}, \quad \psi = \frac{1 - \sqrt{5}}{2}

$φ$ və $ψ$ ədədləri $x^{2} = x + 1$ x^2 = x + 1 tənliyinin kökləridir və Viyet teoreminə görə $φ ψ = - 1$ \varphi\psi = -1.

Qüvvətin açılışı. Bine düsturunu $k$ qüvvətinə yüksəldək və Nyuton binomuna görə mötərizələri açaq:

f_{i}^{k} = \frac{( φ ^{i} - ψ ^{i} ) ^{k}}{( 5 ) ^{k}} = \frac{1}{( 5 ) ^{k}} j = 0 \sum k (- 1)^{j} C_{k}^{j} φ^{i (k - j)} ψ^{ij} = \frac{1}{( 5 ) ^{k}} j = 0 \sum k (- 1)^{j} C_{k}^{j} (φ^{k - j} ψ^{j})^{i}

f_i^k = \frac{(\varphi^i - \psi^i)^k}{(\sqrt{5})^k} = \frac{1}{(\sqrt{5})^k}\sum_{j=0}^{k}(-1)^j C_k^j\, \varphi^{i(k-j)}\psi^{ij} = \frac{1}{(\sqrt{5})^k}\sum_{j=0}^{k}(-1)^j C_k^j\, \left(\varphi^{k-j}\psi^j\right)^i

İşarə edək:

t_{j} = φ^{k - j} ψ^{j}, j = 0, 1, \dots, k

t_j = \varphi^{k-j}\psi^j, \quad j = 0, 1, \ldots, k

$i$ üzrə $1$ -dən $n$ -ə qədər cəmləyək və cəmləmə sırasını dəyişək:

S = i = 1 \sum n f_{i}^{k} = \frac{1}{( 5 ) ^{k}} j = 0 \sum k (- 1)^{j} C_{k}^{j} i = 1 \sum n t_{j}^{i}

S = \sum_{i=1}^{n} f_i^k = \frac{1}{(\sqrt{5})^k}\sum_{j=0}^{k}(-1)^j C_k^j \sum_{i=1}^{n} t_j^{\,i}

Beləliklə, $n$ toplananın cəmi $k + 1$ k + 1 toplananın cəminə gətirildi.

Həndəsi silsilə. Daxili cəm vuruğu $t = t_{j}$ t = t_j olan həndəsi silsilənin cəmidir:

G (t) = i = 1 \sum n t^{i} = ⎩ ⎨ ⎧ \frac{t ( t ^{n} - 1 )}{t - 1}, n, t \neq = 1, t = 1

G(t) = \sum_{i=1}^{n} t^i = \begin{cases} \dfrac{t\,(t^n - 1)}{t - 1}, & t \neq 1, \\[2mm] n, & t = 1 \end{cases}

$t = 1$ t = 1 halı həqiqətən yaranır və ayrıca emal tələb edir (əks halda sıfıra bölmə baş verər). Məsələn, $k$ ədədi $4$ -ə bölünərsə, $j = k /2$ j = k / 2 olduqda alırıq:

t_{k /2} = (φ ψ)^{k /2} = (- 1)^{k /2} = 1

t_{k/2} = (\varphi\psi)^{k/2} = (-1)^{k/2} = 1

$t^{n}$ t^n qüvvəti binar qüvvətə yüksəltmə üsulu ilə $O (lo g n)$ O(\log n) vaxtda hesablanır, buna görə hər toplanan hətta $n = 1 0^{18}$ n = 10^{18} olduqda da tez tapılır.

Vuruqların ardıcıl hesablanması. Hər $j$ üçün $φ$ və $ψ$ ədədlərini yenidən qüvvətə yüksəltməyə ehtiyac yoxdur. Qonşu vuruqlar aşağıdakı münasibətlə bağlıdır:

t_{j + 1} = t_{j} \cdot \frac{ψ}{φ},

t_{j+1} = t_j \cdot \frac{\psi}{\varphi},

buna görə $t_{0} = φ^{k}$ t_0 = \varphi^k qiymətini bir dəfə hesablamaq, sonra isə hər iterasiyada cari qiyməti $ψ / φ$ -yə vurmaq kifayətdir.

Modul üzrə hesablamalar. Həqiqi ədədlər arifmetikası burada yaramır: $p = 1 0^{9} + 7$ p = 10^9 + 7 modulu üzrə dəqiq cavab lazımdır. $a + b 5$ a + b\sqrt{5} şəklində ədədlərlə işləyəcəyik, burada $a$ və $b$ — $p$ modulu üzrə qalıqlardır. Belə ədədlərin toplanması və vurulması aşağıdakı qaydalarla aparılır:

(a + b 5) + (c + d 5) = (a + c) + (b + d) 5, (a + b 5) (c + d 5) = (a c + 5 b d) + (a d + b c) 5

(a + b\sqrt{5}) + (c + d\sqrt{5}) = (a + c) + (b + d)\sqrt{5}, \\ (a + b\sqrt{5})(c + d\sqrt{5}) = (ac + 5bd) + (ad + bc)\sqrt{5}

$a + b 5$ a + b\sqrt{5} şəklində ədədlər $Z_{p} [5]$ \mathbb{Z}_p[\sqrt{5}] meydanını əmələ gətirir. Bu meydanda sıfırdan fərqli istənilən elementin tərsi var:

(a + b 5)^{- 1} = \frac{a - b 5}{a ^{2} - 5 b ^{2}},

(a + b\sqrt{5})^{-1} = \frac{a - b\sqrt{5}}{a^2 - 5b^2},

həm də $a^{2} - 5 b^{2}$ a^2 - 5b^2 məxrəci $p$ modulu üzrə sıfıra bərabər deyil. Bu, həlldəki bütün bölmələrin düzgünlüyünə təminat verir. $φ$ və $ψ$ düsturlarında $2$ -yə bölmə $2^{- 1} mod p = (p + 1) /2$ 2^{-1} \bmod p = (p + 1) / 2 ədədinə vurma ilə əvəz olunur.

2-nin tərs elementi. $p$ modulu üzrə $2$ -nin tərs elementi elə $x$ ədədidir ki, $2 x \equiv 1 (mod p)$ 2x \equiv 1 \pmod{p}.

$x = (p + 1) /2$ x = (p + 1) / 2 ədədinin uyğun gəldiyini yoxlayaq:

$p = 1 0^{9} + 7$ p = 10^9 + 7 — tək sadə ədəddir, buna görə $p + 1$ p + 1 cütdür və $(p + 1) /2$ (p + 1) / 2 — tam ədəddir. O, $p$ -dən kiçikdir, yəni $p$ modulu üzrə adi qalıqdır.
Onu $2$ -yə vuraq: $2 \cdot (p + 1) /2 = p + 1 \equiv 1 (mod p)$ 2 \cdot (p + 1) / 2 = p + 1 \equiv 1 \pmod{p}.

Deməli, $(p + 1) /2$ (p + 1) / 2 məhz $2^{- 1} mod p$ 2^{-1} \bmod p-dir.

Axtarılan cəm tam ədəddir, buna görə yekun $a + b 5$ a + b\sqrt{5} qiymətində $b$ əmsalı mütləq sıfır olacaq, cavab isə $a$ olacaq.

Nümunə

Birinci nümunəyə baxaq: $n = 4$ , $k = 1$ \boldsymbol{k = 1}. $k = 1$ k = 1 olduqda düstur aşağıdakı şəkli alır:

S = \frac{1}{5} (i = 1 \sum 4 φ^{i} - i = 1 \sum 4 ψ^{i})

S = \frac{1}{\sqrt{5}}\left(\sum_{i=1}^{4}\varphi^i - \sum_{i=1}^{4}\psi^i\right)

$φ^{2} = φ + 1$ \varphi^2 = \varphi + 1 münasibətindən istifadə edərək $φ$ -nin qüvvətlərini hesablayaq:

φ = \frac{1 + 5}{2}, φ^{2} = \frac{3 + 5}{2}, φ^{3} = \frac{4 + 2 5}{2}, φ^{4} = \frac{7 + 3 5}{2}

\varphi = \frac{1 + \sqrt{5}}{2}, \quad \varphi^2 = \frac{3 + \sqrt{5}}{2}, \quad \varphi^3 = \frac{4 + 2\sqrt{5}}{2}, \quad \varphi^4 = \frac{7 + 3\sqrt{5}}{2}

Onların cəmi $\frac{15 + 7 5}{2}$ \dfrac{15 + 7\sqrt{5}}{2}-yə bərabərdir. $ψ$ -nin qüvvətləri $5$ \sqrt{5}-in $- 5$ -\sqrt{5} ilə əvəz edilməsindən alınır, buna görə onların cəmi $\frac{15 - 7 5}{2}$ \dfrac{15 - 7\sqrt{5}}{2}-yə bərabərdir. Deməli,

S = \frac{1}{5} (\frac{15 + 7 5}{2} - \frac{15 - 7 5}{2}) = \frac{7 5}{5} = 7,

S = \frac{1}{\sqrt{5}}\left(\frac{15 + 7\sqrt{5}}{2} - \frac{15 - 7\sqrt{5}}{2}\right) = \frac{7\sqrt{5}}{\sqrt{5}} = 7,

bu da cavabla üst-üstə düşür: $1 + 1 + 2 + 3 = 7$ 1 + 1 + 2 + 3 = 7.

Nümunəyə baxaq: $k = 3$ \boldsymbol{k = 3}. Fərqin kubunu açaq:

f_{i}^{3} = \frac{( φ ^{i} - ψ ^{i} ) ^{3}}{( 5 ) ^{3}} = \frac{φ ^{3 i} - 3 φ ^{2 i} ψ ^{i} + 3 φ ^{i} ψ ^{2 i} - ψ ^{3 i}}{5 5}

f_i^3 = \frac{(\varphi^i - \psi^i)^3}{(\sqrt{5})^3} = \frac{\varphi^{3i} - 3\varphi^{2i}\psi^i + 3\varphi^i\psi^{2i} - \psi^{3i}}{5\sqrt{5}}

Silsilələrin vuruqları ( $φ ψ = - 1$ \varphi\psi = -1 bərabərliyindən istifadə edirik):

t_{0} = φ^{3}, t_{1} = φ^{2} ψ = - φ, t_{2} = φ ψ^{2} = - ψ, t_{3} = ψ^{3}

t_0 = \varphi^3, \quad t_1 = \varphi^2\psi = -\varphi, \quad t_2 = \varphi\psi^2 = -\psi, \quad t_3 = \psi^3

Onda

i = 1 \sum n f_{i}^{3} = \frac{1}{5 5} (i = 1 \sum n (φ^{3})^{i} - 3 i = 1 \sum n (- φ)^{i} + 3 i = 1 \sum n (- ψ)^{i} - i = 1 \sum n (ψ^{3})^{i})

\sum_{i=1}^{n} f_i^3 = \frac{1}{5\sqrt{5}}\left(\sum_{i=1}^{n}(\varphi^3)^i - 3\sum_{i=1}^{n}(-\varphi)^i + 3\sum_{i=1}^{n}(-\psi)^i - \sum_{i=1}^{n}(\psi^3)^i\right)

Dörd cəmin hər biri həndəsi silsilənin cəmi düsturu ilə hesablanır. Bunu $n = 3$ n = 3 üçün yoxlayaq. $φ$ -nin qüvvətləri:

φ^{3} = 2 + 5, φ^{6} = 9 + 45, φ^{9} = 38 + 175

\varphi^3 = 2 + \sqrt{5}, \quad \varphi^6 = 9 + 4\sqrt{5}, \quad \varphi^9 = 38 + 17\sqrt{5}

Onda

i = 1 \sum 3 (φ^{3})^{i} = φ^{3} + φ^{6} + φ^{9} = (2 + 5) + (9 + 45) + (38 + 175) = 49 + 225, i = 1 \sum 3 (- φ)^{i} = - φ + φ^{2} - φ^{3} = \frac{- ( 1 + 5 ) + ( 3 + 5 ) - ( 4 + 2 5 )}{2} = - 1 - 5

\sum_{i=1}^{3}(\varphi^3)^i = \varphi^3 + \varphi^6 + \varphi^9 = (2 + \sqrt{5}) + (9 + 4\sqrt{5}) + (38 + 17\sqrt{5}) = 49 + 22\sqrt{5}, \\ \sum_{i=1}^{3}(-\varphi)^i = -\varphi + \varphi^2 - \varphi^3 = \frac{-(1 + \sqrt{5}) + (3 + \sqrt{5}) - (4 + 2\sqrt{5})}{2} = -1 - \sqrt{5}

$ψ$ üçün cəmlər $5$ \sqrt{5}-in $- 5$ -\sqrt{5} ilə əvəz edilməsindən alınır:

i = 1 \sum 3 (- ψ)^{i} = - 1 + 5, i = 1 \sum 3 (ψ^{3})^{i} = 49 - 225

\sum_{i=1}^{3}(-\psi)^i = -1 + \sqrt{5}, \quad \sum_{i=1}^{3}(\psi^3)^i = 49 - 22\sqrt{5}

Tapılmış qiymətləri yerinə yazaq:

i = 1 \sum 3 f_{i}^{3} = \frac{( 49 + 22 5 ) - 3 ( - 1 - 5 ) + 3 ( - 1 + 5 ) - ( 49 - 22 5 )}{5 5} = \frac{50 5}{5 5} = 10

\sum_{i=1}^{3} f_i^3 = \frac{(49 + 22\sqrt{5}) - 3(-1 - \sqrt{5}) + 3(-1 + \sqrt{5}) - (49 - 22\sqrt{5})}{5\sqrt{5}} = \frac{50\sqrt{5}}{5\sqrt{5}} = 10

Nəticə birbaşa hesablama ilə üst-üstə düşür:

f_{1}^{3} + f_{2}^{3} + f_{3}^{3} = 1^{3} + 1^{3} + 2^{3} = 1 + 1 + 8 = 10

f_1^3 + f_2^3 + f_3^3 = 1^3 + 1^3 + 2^3 = 1 + 1 + 8 = 10

$k = 4$ \boldsymbol{k = 4} üçün nümunəyə baxaq (xüsusi hal). Burada

t_{0} = φ^{4}, t_{1} = φ^{3} ψ = - φ^{2}, t_{2} = φ^{2} ψ^{2} = 1, t_{3} = φ ψ^{3} = - ψ^{2}, t_{4} = ψ^{4}

t_0 = \varphi^4, \quad t_1 = \varphi^3\psi = -\varphi^2, \quad t_2 = \varphi^2\psi^2 = 1, \quad t_3 = \varphi\psi^3 = -\psi^2, \quad t_4 = \psi^4

və

i = 1 \sum n f_{i}^{4} = \frac{1}{25} (i = 1 \sum n (φ^{4})^{i} - 4 i = 1 \sum n (- φ^{2})^{i} + 6 n - 4 i = 1 \sum n (- ψ^{2})^{i} + i = 1 \sum n (ψ^{4})^{i})

\sum_{i=1}^{n} f_i^4 = \frac{1}{25}\Biggl(\sum_{i=1}^{n}(\varphi^4)^i - 4\sum_{i=1}^{n}(-\varphi^2)^i + 6n - 4\sum_{i=1}^{n}(-\psi^2)^i + \sum_{i=1}^{n}(\psi^4)^i\Biggr)

Orta toplanan $t_{2} = 1$ t_2 = 1 vuruğuna uyğundur: həndəsi silsilənin cəmi düsturu ona tətbiq olunmur, $1 + 1 + \dots + 1$ 1 + 1 + \ldots + 1 cəmi isə $n$ -ə bərabərdir. Proqramda məhz bu hal ayrıca emal olunur. Məsələn, $n = 3$ n = 3 olduqda alırıq:

f_{1}^{4} + f_{2}^{4} + f_{3}^{4} = 1^{4} + 1^{4} + 2^{4} = 1 + 1 + 16 = 18

f_1^4 + f_2^4 + f_3^4 = 1^4 + 1^4 + 2^4 = 1 + 1 + 16 = 18

Alqoritmin reallaşdırılması

Modul üçün $M O D$ sabitini elan edək.

#define MOD 1000000007

Binomial əmsalların qiymətlərini $C nk$ massivində saxlayacağıq.

vector<long long> Cnk;

$Z_{M O D} [5]$ Z_{MOD} [\sqrt{5}] meydanında arifmetikanı reallaşdırmaq üçün $N u m$ strukturunu elan edək. Struktur $x + y 5$ x + y \sqrt{5} şəklində ədədi saxlayır.

struct Num
{
  long long x, y;
  Num(long long x = 0, long long y = 0) : x(x% MOD), y(y% MOD) {}
};

add funksiyası $Z_{M O D} [5]$ Z_{MOD} [\sqrt{5}] meydanında toplamanı reallaşdırır.

Num add(const Num& a, const Num& b)
{
  return Num((a.x + b.x) % MOD, (a.y + b.y) % MOD);
}

mult funksiyası $Z_{M O D} [5]$ Z_{MOD} [\sqrt{5}] meydanında vurmanı reallaşdırır.

Num mult(const Num& a, const Num& b)
{
  return Num(
    (a.x * b.x + 5 * a.y % MOD * b.y) % MOD,
    (a.x * b.y + a.y * b.x) % MOD
  );
}

C++

pw funksiyası $Z_{M O D} [5]$ Z_{MOD} [\sqrt{5}] meydanında binar qüvvətə yüksəltməni reallaşdırır, burada $e x p$ qüvvət üstü tam ədəddir.

Num pw(Num base, long long exp)
{
  Num res(1, 0);
  while (exp)
  {
    if (exp & 1) res = mult(res, base);
    base = mult(base, base);
    exp >>= 1;
  }
  return res;
}

C++

pw funksiyası $M O D$ modulu üzrə $a^{b}$ a^b qüvvətini sürətli binar qüvvətə yüksəltmə ilə hesablayır.

long long pw(long long a, long long b)
{
  long long res = 1;
  a %= MOD;
  while (b)
  {
    if (b & 1) res = (res * a) % MOD;
    a = a * a % MOD;
    b >>= 1;
  }
  return res;
}

C++

inv funksiyası $Z_{M O D} [5]$ Z_{MOD} [\sqrt{5}] meydanında $a$ elementinin tərs elementini hesablayır.

Əgər

a = x + y 5,

a = x + y \sqrt{5},

olarsa, onda onun tərs elementi belə olacaq:

a^{- 1} = \frac{1}{x + y 5} = \frac{x - y 5}{x ^{2} - 5 y ^{2}}

a^{-1} = \frac{1}{x+y\sqrt{5}} = \frac{x-y\sqrt{5}}{x^2-5y^2}

Num inv(const Num& a)
{
  long long den = (a.x * a.x - 5 * a.y * a.y) % MOD;
  if (den < 0) den += MOD;

  long long invDen = pw(den, MOD - 2);

  return Num(
    a.x * invDen % MOD,
    (MOD - a.y) * invDen % MOD
  );
}

C++

divide funksiyası $Z_{M O D} [5]$ Z_{MOD} [\sqrt{5}] meydanında bölməni reallaşdırır:

\frac{a}{b} = a \cdot b^{- 1}

\frac{a}{b} = a \cdot b^{-1}

Num divide(const Num& a, const Num& b)
{
  return mult(a, inv(b));
}

Proqramın əsas hissəsi. Giriş verilənlərini oxuyuruq.

scanf("%lld %lld", &n, &k);

$C_{k}^{0}, C_{k}^{1}, C_{k}^{2}, ..., C_{k}^{k}$ C_k^0, C_k^1, C_k^2, ..., C_k^k binomial əmsallarını hesablayırıq və onları $C nk$ massivinə yazırıq. Qeyd edək ki,

C nk [i] = C_{k}^{i} = C_{k}^{i - 1} \cdot \frac{k - i + 1}{i}

Cnk[i] = C_k^i = C_k^{i-1} \cdot \frac{k - i + 1}{i}

Cnk.resize(k + 1);
Cnk[0] = 1;
for (i = 1; i <= k; i++)
{
  Cnk[i] = Cnk[i - 1] * (k - i + 1) % MOD;
  Cnk[i] = Cnk[i] * pw(i, MOD - 2) % MOD;
}

C++

$in v 2 = 2^{- 1} mod M O D = (M O D + 1) /2$ inv2 = 2^{-1} \mod MOD = (MOD + 1) / 2 qiymətini hesablayırıq.

long long inv2 = (MOD + 1) / 2;

Sabitləri inisializasiya edirik: $p hi = ϕ = \frac{1 + 5}{2}$ phi = \phi = \frac{1 + \sqrt{5}}{2} və $p s i = ψ = \frac{1 - 5}{2}$ psi = \psi = \frac{1 - \sqrt{5}}{2}.

Num phi(inv2, inv2);
Num psi(inv2, MOD - inv2);

$r a t i o = ψ / ϕ$ ratio = \psi / \phi qiymətini hesablayırıq.

Num ratio = divide(psi, phi);

$Z_{M O D} [5]$ Z_{MOD} [\sqrt{5}] meydanında $1$ və $- 1$ sabitlərini inisializasiya edirik.

Num one(1, 0);
Num minus_one(MOD - 1, 0);

Cavabı $r es$ dəyişənində toplayacağıq.

Num res(0, 0);

$t = ϕ^{k}$ t = \phi^k qiymətini inisializasiya edirik. Sonra dövrdə bu qiyməti $r a t i o$ -ya vuraraq aşağıdakıları alacağıq:

ϕ^{k}, ϕ^{k - 1} ψ, ϕ^{k - 2} ψ^{2}, ..., ϕ ψ^{k - 1}, ψ^{k}

\phi^k, \phi^{k-1}\psi, \phi^{k-2}\psi^2, ..., \phi\psi^{k-1}, \psi^k

Num t = pw(phi, k);

$r es$ dəyişənində aşağıdakı cəmi hesablayırıq:

i = 1 \sum n f_{i}^{k} = \frac{1}{( 5 ) ^{k}} j = 0 \sum k (- 1)^{j} C_{k}^{j} i = 1 \sum n (ϕ^{k - j} ψ^{j})^{i}

\sum_{i=1}^{n} f_i^k = \frac{1}{(\sqrt{5})^k} \sum_{j=0}^{k} (-1)^j C_k^j \sum_{i=1}^{n} \left(\phi^{k-j}\psi^j\right)^i

Axtarılan cəm $k + 1$ k + 1 toplanandan ibarətdir. Buna görə $k + 1$ k + 1 iterasiya yerinə yetiririk.

for (j = 0; j <= k; j++)
{
  Num term;

Bu anda $t = ϕ^{k - j} ψ^{j}$ t = \phi^{k-j} \psi^j. Həndəsi silsilənin cəmini hesablayırıq:

t er m = i = 1 \sum n t^{i} = \frac{t ( t ^{n} - 1 )}{t - 1}

term = \sum_{i=1}^{n} t^i = \frac{t(t^n-1)}{t-1}

Lakin $t = 1$ t = 1 halını ayrıca emal etmək lazımdır, çünki həndəsi silsilənin cəmi düsturunda $0$ -a bölmə olacaq. $t = 1$ t = 1 olduqda cəm $1 + 1 + 1 + ... + 1$ 1 + 1 + 1 + ... + 1 ( $n$ dəfə) şəklini alır və $n$ -ə bərabərdir.

  if (t.x == 1 && t.y == 0)
    term = Num(n % MOD, 0);
  else
  {
    Num tn = pw(t, n);
    Num num = add(tn, minus_one);     // t^n - 1
    term = mult(t, num);              // t * (t^n - 1)
    Num den = add(t, minus_one);      // t - 1
    term = divide(term, den);         // t * (t^n - 1) / (t - 1)
  }

C++

$t er m = (- 1)^{j} C_{k}^{j} \cdot t er m$ term = (-1)^j C_k^j \cdot term qiymətini hesablayırıq.

  long long coef = Cnk[j];
  if (j & 1) coef = MOD - coef;

  term.x = term.x * coef % MOD;
  term.y = term.y * coef % MOD;

Növbəti $t er m$ toplananını $r es$ nəticəsinə əlavə edirik.

  res = add(res, term);

$t$ -ni $r a t i o$ -ya vururuq və $t = ϕ^{k - j - 1} ψ^{j + 1}$ t = \phi^{k-j-1} \psi^{j + 1} alırıq.

  t = mult(t, ratio);
}

$r es$ -i $(5)^{k}$ (\sqrt{5})^k-ya bölmək qalır.

Num sqrt5(0, 1);
Num sqrt5k = pw(sqrt5, k);
res = divide(res, sqrt5k);

Cavabı çap edirik.

printf("%lld\n", res.x);