Решение задачи Числа Фибоначчи - 3 с Acmp

С пояснением   Просмотров: 136


Последовательностью Фибоначчи называется последовательность чисел \(F_0 = 1, F_1 = 1, ..., F_k = F_{k-1} + F_{k-2}, \,\,k > 1\)

Требуется найти наибольший общий делитель двух чисел Фибоначчи.

Код

#include <bits/stdc++.h>

using namespace std;

int main()
{

    int i, j;
    cin >> i >> j;
    int mx = max(i, j);
    vector<long long> a(mx);
    a[0] = 1, a[1] = 1;
    for(int k = 2; k < mx; ++k){
        a[k] = (a[k - 1] + a[k - 2]) % 1000000000;
    }
    cout << a[__gcd(i, j) - 1] % 1000000000;

    return 0;
}

         

Администратор Photo Автор: Администратор


Код

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int i, j;
    cin >> i >> j;
    int mx = __gcd(i, j), a0 = 1, a1 = 1, a;
    for(int k = 2; k < mx; ++k){
        a = (a0 + a1) % 1000000000;
        a0 = a1;
        a1 = a;
    }
    cout << a1;
    return 0;
}

         

Администратор Photo Автор: Администратор


Последовательность Фибоначчи выглядит следующим образом:
\( 1, 1, 2, 3, 5, 8, 13, 21 \)
Чтобы не было переполнения long long, нужно присвоить элементу массива сумму двух предыдущих элементов по модуля \( {10}^9 \).
В фибоначчиевой последовательности есть такое свойство:
\( НОД(F_m, F_n) = F_{НОД(m, n)} \)


Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться