ACPC 2014 A.Game of Peace
题目描述：
从(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));
}
}
