2421. Fibonacci
numbers
As is well known, the
Fibonacci sequence is defined as follows:
F0 =
0,
F1 =
1,
Fn = Fn – 1 + Fn
– 2, n > 1
It is named
after the Italian mathematician Leonardo Fibonacci, also known as Leonardo of
Pisa.
Given two
integers n and m, find the greatest common divisor of Fn
and Fm.
Input. Each line represents a single test case and 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 on a separate line the value of GCD(Fn, Fm) modulo 108.
|
Sample
input |
Sample
output |
|
2 3 1 1 100 200 |
1 1 61915075 |
SOLUTION
Fibonacci numbers
Algorithm analysis
It is known that Fibonacci numbers
satisfy the following identity:
GCD(Fn,
Fm) = FGCD(n,m)
This means
that the problem reduces to computing the k-th Fibonacci number modulo 108, where
k = GCD(n, m)
Since n, m ≤ 1018, we have k
≤ 1018. Therefore, it is necessary to compute the value of Fk mod 108 in O(log2k) time.
Theorem.
To efficiently compute Fibonacci numbers, it is convenient to use matrix
exponentiation. It is known that:
Base case. For k = 1, we have:
,
which is true since F0
= 0, F1 = 1, F2 = 1.
Inductive step. Assume
that the formula holds for k. Then, for k + 1:
= 
= 
Thus, the formula is valid
for all k ≥ 1.
It remains to implement
raising a matrix to the power k using fast exponentiation in O(log2k) time.
Example
Fibonacci numbers are
defined as follows:
Let’s compute the
Fibonacci numbers using matrix exponentiation:
Algorithm implementation – operators overloading
Declare the constant MOD,
modulo which all computations will be performed.
#define MOD 100000000
The function gcd
computes the greatest common divisor of two numbers a and b.
long long gcd(long long a, long long b)
{
return (!b) ? a : gcd(b, a % b);
}
Let us declare a Matrix
class and write its 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;
}
Let us overload the matrix multiplication operator. All
computations are performed modulo 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;
}
Next,
overload the operator for raising 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);
}
};
The
function fib returns the n-th Fibonacci number Fn
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 FGCD(n, m).
while(scanf("%lld
%lld",&n,&m) == 2)
{
d = gcd(n,m);
printf("%lld\n",fib(d));
}
Algorithm implementation – functions
Declare the constant MOD,
modulo which all computations will be performed.
#define MOD 100000000
The function gcd
computes the greatest common divisor of two numbers a and b.
long long gcd(long long a, long long b)
{
return (!b) ? a : gcd(b, a % b);
}
Declare the Matrix structure –
a 2 ? 2
matrix. By default, the identity matrix is created, which is convenient for
exponentiation.
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_) {}
};
The function multiply
multiplies two 2 ? 2
matrices using the standard formula.
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
);
}
The function power
implements binary exponentiation of the matrix base to the power 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;
}
The function fib
computes the n-th Fibonacci number modulo 108 using the
matrix method.
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)
}
The main part of the
program. Read the input data, compute, and print the value of FGCD(n, m).
while (scanf("%lld %lld", &n, &m) == 2)
{
d = gcd(n, m);
printf("%lld\n", fib(d));
}
Algorithm implementation – memoization
The following identity is
known for Fibonacci numbers:
Fn+m
= Fm ∙ Fn+1 + Fm-1
∙ Fn
From it, the following
special cases directly follow:
·
if m = n, then F2n = Fn ∙ Fn+1 + Fn-1 ∙ Fn.
·
if m = n + 1, then F2n+1 = Fn+1
∙ Fn+1 + Fn ∙ Fn.
These formulas allow
Fibonacci numbers to be computed using a “divide and conquer” approach,
reducing the computation of Fn to values with indices approximately half as large.
The base cases are handled
separately:
F0 =
0, F1 =
F2 = 1
With this approach, the
recursion depth is proportional to log2n,
and the time complexity of the algorithm is O(log2n).
Declare the constant MOD,
modulo which all computations will be performed.
#define MOD 100000000
Declare a variable F of type map
to store (memoize) the Fibonacci numbers that have already been computed.
map<long long, long long> F;
The function gcd
computes the greatest common divisor of two numbers a and b.
long long gcd(long long a, long long b)
{
return (!b) ? a : gcd(b,a % b);
}
The function fib
computes the n-th Fibonacci number modulo 108.
long long fib(long long n)
{
The base cases are handled
separately.
if (n == 0) return 0;
if (n == 1) return 1;
if (n == 2) return 1;
If the value of Fn has already been computed and stored in F, it is returned
immediately without recomputation.
if (F[n]) return
F[n];
Next, we use the decomposition
of the number n into:
·
n = 2k + 1 – odd case: 
.
·
n = 2k – even case: 
.
long long k = n / 2;
Store and return the
result.
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;
}
The main part of the
program. Read the input data, compute, and print the value of FGCD(n, m).
while(scanf("%lld %lld",&a,&b)
== 2)
{
d = gcd(a,b);
printf("%lld\n",fib(d));
}
Java implementation
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();
}
}