我是靠谱客的博主 大力大侠,最近开发中收集的这篇文章主要介绍牛客小白月赛——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题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(49)

评论列表共有 0 条评论

立即
投稿
返回
顶部