K - Last Defence Gym - 100548K (2014 Xi'an site)

题目给定两个数S0,S1问|Si-Si-1|中有多少不同的数
区域赛铜牌题，思维难度是真的有。首先我们要了解辗转相减后的结果是a%b也就是说a-b=c b-c=d…这样减下去的结果就是a%b
然后其中有的个数是floor(a/b)+(a%b==0)
这样我们就可以跟欧几里得算法那样的感觉那样，进行递归计算，这样使得可以一直相减下去最后需要特判一些情况
如果a==b那么是2 如果都是0那么是1 如果是一0一其他数那么是2，如果a<b 那么是f(a,b-a)+1(要加上b)

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
long long f(long long a,long long b)
{
	if(a<b) swap(a,b);
	if(a%b==0) return a/b+1;
	else return a/b+f(a%b,b);
}
int main()
{
	int t;
	scanf("%d",&t);
	for(int k=1;k<=t;k++)
	{
		long long a,b;
		scanf("%lld%lld",&a,&b);
		printf("Case #%d: ",k);
		if(a==b) 
		{
			if(a==0) puts("1");
			else puts("2");
		}
		else
		{
			if(a==0||b==0) puts("2");
			else if(a>b) printf("%lld\n",f(a,b));
			else printf("%lld\n",f(a,b-a)+1LL);
		}
	}
}