Last Defense 西安现场赛 欧几里得出发的应用

　　这道题的意思是给你两个数A, B, s0 = A, s1 = B, si = |si-1 - si-2|， 让你求出里面有几个不同的数， 首先我们可以确定对于数y和x，y一定能写成kx+b的形式，在数列的生成过程中，会出现kx+b、x、(k-1)x+b、(k-2)x+b、x、...、2x+b、x、x+b、b、x，其中出现的不同数字个数就是(kx+b)/ x，之后问题变成了数x和b的问题，最后可以发现这就是一个辗转相除法的过程。每做一次辗转相除gcd(x,y)，不同数字个数就多了x/ y。最后加上一个末尾出现的0。

还有一些特殊情况需要考虑，比如有数字是0。。 代码如下：

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
LL a, b;


int main()
{
    int T;
    cin>>T;
    int kase = 0;
    while(T--)
    {
        cin>>a>>b;
        if(a==0 && b==0)
        {
            printf("Case #%d: 1
", ++kase);
            continue;
        }
        else if(a==0 || b==0)
        {
            printf("Case #%d: 2
", ++kase);
            continue;
        }
        LL res = 0;
        while(1)
        {
            if(a < b) swap(a, b);
            if(b == 0) break;
            res += a/b;
            LL tp = b;
            b = a%b;
            a = tp;
        }
        printf("Case #%d: %I64d
", ++kase, res+1);
    }
    return 0;
}