『算法-ACM 竞赛-数学-数论』HDU 1495 非常可乐

Description
大家一定觉的运动以后喝可乐是一件很惬意的事情，但是 seeyou 却不这么认为。因为每次当 seeyou 买了可乐以后，阿牛就要求和 seeyou 一起分享这一瓶可乐，而且一定要喝的和 seeyou 一样多。但 seeyou 的手中只有两个杯子，它们的容量分别是 N 毫升和 M 毫升 可乐的体积为 S （S<101）毫升　(正好装满一瓶) ，它们三个之间可以相互倒可乐 (都是没有刻度的，且 S==N+M，101 ＞ S ＞ 0，N ＞ 0，M ＞ 0) 。聪明的 ACMER 你们说他们能平分吗？如果能请输出倒可乐的最少的次数，如果不能输出”NO”。
Input
三个整数 : S 可乐的体积 , N 和 M 是两个杯子的容量，以”0 0 0”结束
Output
如果能平分的话请输出最少要倒的次数，否则输出”NO”
Sample Input
7 4 3
4 1 3
0 0 0
Sample Output
NO
3
Solution
设两个小瓶子容积分别为 a,b，问题转化成通过两个小瓶子的若干次倒进或倒出操作得到(a+b)/2 体积的可乐，设两个小瓶子被倒进或倒出 x 次和 y 次（这里的 x 和 y 是累加后的操作，即 x=第一个瓶子倒出的次数-倒进的次数，y=第二个瓶子倒出的次数-倒进的次数），那么问题转化成：

所以|x+|y|的最小值为(c+d)/2，通过 x 和 y 的通解形式显然可以看出 x 和 y 一正一负，不妨设 x<0，那么就是往第一个小瓶子倒进 x 次，第二个小瓶子倒出 y 次，但是由于瓶子容积有限，所以倒进倒出操作都是通过大瓶子来解决的，一次倒进操作后为了继续使用小瓶子还要将小瓶子中可乐倒回大瓶子中，倒出操作同理，所以总操作次数是(c+d)/2*2=c+d，但是注意最后剩下的(a+b)/2 体积的可乐一定是放在两个小瓶子中较大的那个中，而不是再倒回到大瓶子中，所以操作数要减一，答案就是 c+d-1

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,c;
	while( ~ scanf("%d%d%d",&a,&b,&c))
	{
		if(a == 0 && b == 0 && c == 0)
		break;
		int g  = __gcd(b,c);
		if((b + c) / g % 2)
		{
			cout << "NO" << endl;
			continue;
		}
		cout << (b + c) / g - 1 << endl;
	}
	return 0;
}