A21444.斐波那契公约数

提高+/省选-

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

对于 Fibonacci 数列:

fi={[i=1]i1fi1+fi2i>1 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 取模。

输入输出样例

  • 输入#1

    4 7

    输出#1

    1

说明/提示

数据规模与约定

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