概述
题目描述
链接: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题所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复