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