2421. Числа Фибоначчи
Как известно,
последовательность Фибоначчи определяется следующим образом:
F0 =
0,
F1 =
1,
Fn = Fn – 1 + Fn
– 2, n > 1
Она названа в
честь итальянского математика Леонардо Фибоначчи, также известного как Леонардо
из Пизы.
Заданы два целых
числа n и m. Найдите
наибольший общий делитель чисел Fn и Fm.
Вход. Каждая строка является отдельным тестом и содержит два целых
числа n и m (1 ≤ n, m ≤ 1018).
Количество тестов не превышает 1000.
Выход. Для каждого теста выведите
в отдельной строке значение НОД(Fn,
Fm), взятое по модулю 108.
|
Пример
входа |
Пример
выхода |
|
2 3 1 1 100 200 |
1 1 61915075 |
РЕШЕНИЕ
числа
Фибоначчи
Анализ алгоритма
Известно, что для чисел Фибоначчи
выполняется равенство:
НОД(Fn, Fm) = FНОД(n,m)
Это
означает, что задача сводится к вычислению k-го числа Фибоначчи по
модулю 108,
где
k = НОД(n, m)
Так как n, m ≤ 1018, то k ≤ 1018. Следовательно, необходимо вычислить значение
Fk mod 108 за время O(log2k).
Теорема. Для
быстрого вычисления чисел Фибоначчи удобно использовать матричное возведение в
степень. Известно, что:
База индукции. При k = 1 имеем:
,
что верно так
как F0
= 0, F1 = 1, F2 = 1.
Шаг индукции. Предположим, что формула верна для k.
Тогда для k + 1:
= 
= 
Таким образом, формула
верна для всех k ≥ 1.
Осталось
реализовать возведение матрицы в степень k с использованием быстрого возведения
в степень за время O(log2k).
Пример
Числа Фибоначчи
имеют вид:
Вычислим числа Фибоначчи с
помощью возведения в степень матрицы:
Реализация алгоритма –
перегрузка операторов
Объявим константу
MOD, по модулю
которой будут производиться вычисления.
#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;
}
Перегрузим оператор умножения матриц.
Все вычисления выполняем по модулю MOD = 108.
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;
}
Перегрузим оператор возведения матрицы в степень n.
Временная сложность алгоритма составляет O(log2n).
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);
}
};
Функция fib
возвращает n-ое число Фибоначчи Fn по модулю 108.
long long
fib(long long
n)
{
Matrix res(1,1,1,0);
res = res ^ n;
return res.b;
}
Основная часть
программы. Читаем входные данные, вычисляем и выводим значение FНОД(n,
m).
while(scanf("%lld
%lld",&n,&m) == 2)
{
d = gcd(n,m);
printf("%lld\n",fib(d));
}
Реализация алгоритма –
функции
Объявим константу
MOD, по модулю
которой будут производиться вычисления.
#define MOD 100000000
Функция gcd вычисляет наибольший общий делитель двух чисел a и b.
long long gcd(long long a, long long b)
{
return (!b) ? a : gcd(b, a % b);
}
Объявим структуру Matrix – матрицу размера 2 ? 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_) {}
};
Функция multiply
перемножает две матрицы 2 ? 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
);
}
Функция power реализует бинарное
возведение матрицы base в степень exp.
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;
}
Функция fib вычисляет n-е число Фибоначчи по модулю 108
с использованием матричного метода.
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)
}
Основная часть
программы. Читаем входные данные, вычисляем и выводим значение FНОД(n,
m).
while (scanf("%lld %lld", &n, &m) == 2)
{
d = gcd(n, m);
printf("%lld\n", fib(d));
}
Реализация алгоритма – запоминание
Для чисел Фибоначчи
известно следующее тождество:
Fn+m
= Fm ∙ Fn+1 + Fm-1
∙ Fn
Из него непосредственно
следуют частные случаи:
·
если m = n, то F2n = Fn ∙ Fn+1 + Fn-1 ∙ Fn.
·
если m = n + 1, то F2n+1 = Fn+1
∙ Fn+1 + Fn ∙ Fn.
Эти формулы позволяют
вычислять числа Фибоначчи методом “разделяй и властвуй”, сводя вычисление Fn к значениям с примерно
вдвое меньшими индексами.
Отдельно обрабатываются
базовые случаи:
F0 =
0, F1 =
F2 = 1
Благодаря такому подходу
глубина рекурсии пропорциональна log2n,
а временная сложность алгоритма составляет O(log2n).
Объявим константу
MOD, по модулю
которой будут производиться вычисления.
#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-е число Фибоначчи по модулю 108.
long long fib(long long n)
{
Отдельно обрабатываем базовые
случаи.
if (n == 0) return 0;
if (n == 1) return 1;
if (n == 2) return 1;
Если значение Fn уже было вычислено ранее и сохранено в F, оно возвращается сразу, без
повторных вычислений.
if (F[n]) return
F[n];
Далее
используем разложение числа n на:
·
n = 2k + 1 – нечётный случай: 
.
·
n = 2k – чётный случай: 
.
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).
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();
}
}