A2357. 斐波那契公约数
编程题
提高+/省选-
知识点
题目描述
对于 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)$。
$$ 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
1
说明/提示
#### 数据规模与约定
- 对于 $100\%$ 的数据，保证 $1 \leq n, m \leq 10^9$。
P1306
- 对于 $100\%$ 的数据，保证 $1 \leq n, m \leq 10^9$。
P1306