2421. Fibonacci numbers
As is known, the Fibonacci
sequence is defined as:
F(0) =
0, F(1) = 1, F(n) = F(n – 1) + F(n – 2) (äëÿ âñåõ n >
1).
It was named after the
Italian mathematician Leonardo Fibonacci, also known as Leonardo of Pisa.
Given the values of n and m, find the greatest common divisor of F(n) and F(m).
Input. Each line is a separate test
case that contains two integers n and
m (1 ≤ n, m
≤ 1018). The number of test cases does not exceed 1000.
Output. For each test case print in
a separate line the value of GCD(F(n),
F(m)), taken by modulo 108.
|
Sample input |
Sample output |
|
2 3 1 1 100 200 |
1 1 61915075 |
SOLUTION
Fibonacci numbers
Algorithm analysis
It is known that GCD(F(n), F(m)) = F(GCD(n,m)). That is, in the problem you should
find the k-th Fibonacci number, taken
modulo 108, where k = GCD(n,m).
Since n, m ≤ 1018, then k ≤ 1018. Therefore, it is necessary to compute the value of F(k)
mod 108 in time O(log2k).
Theorem. 
.
Base if induction. For k = 1: 
, which is true since
F0 = 0, F1 = 1,
F2 = 1
Induction step. 
It remains to
implement the exponentiation
of the matrix to the power of k in time
O(log2k).
Algorithm realization
Declare the class Matrix and the constructor.
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;
}
Overload the matrix multiplication
operator. All computations are carried out
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;
}
Overload the operator of exponentiation a matrix to the power n.
The time complexity of the algorithm is 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);
}
};
Function fib(n) returns the n-th Fibonacci number F(n)
modulo 108.
long long fib(long long n)
{
Matrix res(1,1,1,0);
res = res ^ n;
return res.b;
}
The main part of
the program. Read the
input data, compute and print the value of F(GCD(n, m)). The function
gcd computes the greatest common divisor of two
numbers.
while(scanf("%lld %lld",&n,&m) == 2)
{
d = gcd(n,m);
printf("%lld\n",fib(d));
}
Algorithm realization – memoization
It is known that Fn+m
= Fm Fn+1 + Fm-1
Fn.
·
if m = n, then F2n
= Fn Fn+1
+ Fn-1 Fn.
·
if m = n + 1, then F2n+1 = Fn+1
Fn+1 + Fn Fn.
Process the cases F0 =
0 and F1 =
F2 =1 separately. Time complexity is 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 realization
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();
}
}