斐波那契公约数 - Luogu - 题目详情 - 云斗学院

ID: 304

远端评测题

1000ms

125MiB

难度: 5

上传者:

标签>

数学

倍增

线性结构

递归

斐波那契,Fibonacci

题目描述

对于 Fibonacci 数列：

f_i = \begin{cases} [i = 1] & i \leq 1 \\ f_{i - 1} + f_{i - 2} & i \gt 1 \end{cases}

请求出 $f_n$ 与 $f_m$ 的最大公约数，即 $\gcd(f_n, f_m)$ 。

输入格式

一行两个正整数 $n$ 和 $m$ 。

输出格式

输出一行一个整数，代表 $f_n$ 和 $f_m$ 的最大公约数。答案请对 $10^8$ 取模。

输入数据 1

4 7

输出数据 1

提示

数据规模与约定

对于 $100\%$ 的数据，保证 $1 \leq n, m \leq 10^9$ 。