#P1306. 斐波那契公约数

    ID: 350 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>数论数学倍增线性结构递归斐波那契Fibonacci

斐波那契公约数

题目描述

对于 Fibonacci 数列:

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

请求出 fnf_nfmf_m 的最大公约数,即 gcd(fn,fm)\gcd(f_n, f_m)

输入格式

一行两个正整数 nnmm

输出格式

输出一行一个整数,代表 fnf_nfmf_m 的最大公约数。答案请对 10810^8 取模。

4 7
1

提示

数据规模与约定

  • 对于 100%100\% 的数据,保证 1n,m1091 \leq n, m \leq 10^9