华华对月月的忠诚

题目描述

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

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。