HDU 1495 非常可乐

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Sample Input - 输入样例

7 4 3
4 1 3
0 0 0

Sample Output - 输出样例

NO
3

题解

不是很想用搜索，发现讨论有数学方法就想试试。然而题目真是大坑，两杯的总容量等于可乐的一半就能结束了。作为渣渣看了别人的题解也是ax+by的式子才放了个心……

为了看着爽，N和M直接换成ab。总操作次数为T，求T最小值。 x or y 表示倒入操作（+1）和倒出操作（-1）迭加的最终状态。 最终n次倒入产生2n-1次操作，最终n次倒出产生2n次操作。

此处先直接目测特解：

虽然现在还没求出通解，不过由于x，y必须满足整数，那么直接设通解：

带入方程，得：

此处强行特解：m = b, n = -a

得原方程的通解：

则：

由于这里的a, b是由原方程未化简直接带入的产物，T取最小值时，k=0，取(a + b)/GCD(a, b)

乍一看不是都有解了？题目可是明显有无解的情况，这个时候就要进行无解判断。
我们已知有解情况下a + b =偶数
下面推导有效解：

代码 C++

 1 #include <cstdio>
 2 int GCD(int a, int b){
 3     int c;
 4     while (c = a%b) a = b, b = c;
 5     return b;
 6 }
 7 int main(){
 8     int opt, a, b;
 9     while (scanf("%d%d%d", &opt, &a, &b), opt){
10         opt /= GCD(a, b);
11         if (--opt & 1) printf("%d\n", opt);
12         else puts("NO");
13     }
14     return 0;
15 }