数论-斐波那契练习题一-斐波那契中的gcd

题面

题目描述

对于Fibonacci数列

:1,1,2,3,5,8,13……大家应该很熟悉吧~~~但是现在有一个很“简单”问题:第n项和第m项的最大公约数是多少?
输入输出格式
输入格式:
两个正整数n和m。(n,m<=10^9)
注意:数据很大

输出格式:

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

输入输出样例

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

分析

其实只要明确一个问题就可以了:
$$gcd(F[n],F[m])=F(gcd(n,m))$$
好像有这么一个结论:欧几里得算法最差的情况下就是斐波那契数列相邻的两项。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
long long n,m,a[1005000];
int main()
{

a[1]=1;
a[2]=1;
scanf("%d%d",&n,&m);
for(int i=3;i<=__gcd(n,m);i++)
a[i]=(a[i-1]+a[i-2])%100000000;
printf("%d\n",a[__gcd(n,m)]);

return 0;
}
文章目录
  1. 1. 题面
    1. 1.1. 题目描述
    2. 1.2. 输出格式:
    3. 1.3. 输入输出样例
  2. 2. 分析
  3. 3. code