题目描述

月月要参加学校的信息学集训,晚上不能陪华华聊天了。不过为了防止华华去和别的小姐姐聊天,浪费时间影响学习,所以月月给华华布置了一项任务。月月给了华华一个类似斐波那契数列的东西,这个数列满足:

F1=A,F2=B,Fi=Fi−1+Fi−2(i>2)

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

输入描述:
输入一行三个正整数A,B,N。

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

思路:
这道题其实考察裴蜀定理,与上次同济大学网络赛中的一道题有非常相似之处,在这里贴出来,希望对大家有用。传送门:
https://ac.nowcoder.com/acm/contest/5477/A
裴蜀定理具体如下:
裴蜀定理(或贝祖定理)得名于法国数学家艾蒂安·裴蜀,说明了对任何整数a、b和它们的最大公约数d,关于未知数x和y的线性不定方程(称为裴蜀等式):若a,b是整数,且gcd(a,b)=d,那么对于任意的整数x,y,ax+by都一定是d的倍数,特别地,一定存在整数x,y,使ax+by=d成立。
———引自百度百科
由裴蜀定理可知,要求gcd(FN,FN+1),只要求出gcd(A,B)就可以了,这两者是相等的。并且C++函数库中已经封装了——gcd(a,b)用来求a与b之间的最大公约数,我们只需要套用就可以了。
代码如下:

#include<iostream>
#include<algorithm>

using namespace std;
char  N[100010];
int main()
{
    long long int A,B;
    cin>>A>>B;
    cin>>N;
    cout<<__gcd(A,B)<<endl;
    return 0;
}

求牛币,QWQ。