P1306 斐波那契公约数

    • 475通过
    • 1.3K提交
  • 题目提供者keyingkai
  • 标签 倍增 数论,数学 斐波那契,Fibonacci 线性结构 递归
  • 难度 提高+/省选-
  • 时空限制 1s / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 推荐的相关题目

    题目描述

    对于Fibonacci数列:1,1,2,3,5,8,13......大家应该很熟悉吧~~~但是现在有一个很“简单”问题:第n项和第m项的最大公约数是多少?

    输入输出格式

    输入格式:

    两个正整数n和m。(n,m<=10^9)

    注意:数据很大

    输出格式:

    Fn和Fm的最大公约数。

    由于看了大数字就头晕,所以只要输出最后的8位数字就可以了。

    输入输出样例

    输入样例#1: 复制
    4 7
    输出样例#1: 复制
    1

    说明

    用递归&递推会超时

    用通项公式也会超时

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。