牛客小白月赛——G题

题目描述

链接：https://ac.nowcoder.com/acm/contest/392/G

月月给了华华一个类似斐波那契数列的东西，这个数列满足：F1=A,F2=B,Fi=Fi−1+Fi−2(i>2)F1=A,F2=B,Fi=Fi−1+Fi−2(i>2)月月希望华华求出gcd(FN,FN+1)gcd(FN,FN+1)。月月认为，求这个东西需要很长的时间，所以华华就没有机会去和其他小姐姐聊天了。华华自然对月月十分忠诚，选择求出F的每一位后计算答案。但是比赛中的你看到这一题，就没必要那么老实了。现在给定A、B、N，请你求出月月要求的那个数字。答案可能很大，但是不取模。

输入描述:

输入一行三个正整数A，B，N。

输出描述:

输出一行一个正整数表示答案。

输入

2 4 5

输出

2

备注

1≤A≤B≤1017，1≤N≤10^100000，也就是说N的长度不超过10 ^ 5

题解:
看到N这么大，就可以猜到这题和N没关系。被 吓跑的同学后悔吧~
令1 <= A <= B ，我们知道gcd(A,B) = gcd(A,B-A)。
由于 Fi = Fi-1 + Fi-2，则 gcd(FN,FN+1) = gcd(FN,FN-1+FN) = gcd(FN,FN-1) = gcd(FN-1,FN)
这样递归下去，最终可以得到 gcd(FN,FN+1) = gcd(F1,F2)。
所以本题就是求gcd(A,B) ，时间复杂度 O(log(max(A,B)))。

#include<stdio.h>
#include<string.h>
typedef long long ll;
ll gcd(ll a,ll b)
{
    if(b==0)return a;
    else return gcd(b,a%b);
}
char n[100005];
int main(void)
{
    ll a,b;
    scanf("%lld%lld",&a,&b);
    scanf("%s",n);
    printf("%lldn",gcd(a,b));
    return 0;
}

最后

以上就是大力大侠最近收集整理的关于牛客小白月赛——G题的全部内容，更多相关牛客小白月赛——G题内容请搜索靠谱客的其他文章。