图片说明
图片说明
题目描述：
从(x,0)开始，每次的操作就是都把多的那个复制一下加给少的那个，做了N次操作后，会产生bug，即多的那个会+y，后面不会再出现bug，问M次后，两个数的gcd是多少。
解题思路：
这种叠加的题目首先考虑一下斐波那契数列。这道题写写样例就知道确实是关于斐波那契数列的。加了y以后，关于y的系数也是斐波那契数列。但是n和m的范围都特别大，会爆longlong。
于是你想用个大数模板，结果居然超了内存。最终，你不得不向打表势力低头，于是你发现i>=n
的所有gcd都相同。
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+7;
ll fib[maxn];
int main()
{
    fib[0] = 0;
    fib[1] = 1;
    for(int i = 2; i < maxn; i++) fib[i] = fib[i-1]+fib[i-2];
    ll T,x, n, y, m, cnt = 0;
    cin >> T;
    while(T--)
    {
        cin >> x >> n >> y >> m;

        ll a = fib[n + 1] * x +  y;
        ll b = fib[n] * x;

        printf("Case %lld: %lld\n",++cnt,__gcd(a, b));
    }
}