描述 Description
Winy 是一家酒吧的老板，他的酒吧提供两种体积的啤酒，a ml 和 b ml，分别使用容积为 a ml 和 b ml 的酒杯来装载。
酒吧的生意并不好。Winy 发现酒鬼们都非常穷。有时，他们会因为负担不起 aml 或者 bml 啤酒的消费，而不得不离去。因此，Winy 决定出售第三种体积的啤酒 (较小体积的啤酒)。
Winy 只有两种杯子，容积分别为 a ml 和 b ml，而且啤酒杯是没有刻度的。他只能通过两种杯子和酒桶间的互相倾倒来得到新的体积的酒。
为了简化倒酒的步骤，Winy 规定：
（1）a≥b；
（2）酒桶容积无限大，酒桶中酒的体积也是无限大 (但远小于桶的容积)；
（3）只包含三种可能的倒酒操作：
①将酒桶中的酒倒入容积为 b ml 的酒杯中；
②将容积为 a ml 的酒杯中的酒倒入酒桶；
③将容积为 b ml 的酒杯中的酒倒入容积为 a ml 的酒杯中。
（4）每次倒酒必须把杯子倒满或把被倾倒的杯子倒空。
Winy 希望通过若干次倾倒得到容积为 a ml 酒杯中剩下的酒的体积尽可能小，他请求你帮助他设计倾倒的方案
输入格式 InputFormat
两个整数 a 和 b（0
样例输出 SampleOutput
1
1 2
代码 Code
很容易知道 a 中的酒的最小体积为 a 和 b 的最大公约数，于是求 exgcd，然后调整 x 和 y 到 x 为非正数且尽量大且 y 为非负数即可。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int i,j,t,n,m,l,r,k,z,y,x;
int a,b;
int exgcd(int a,int b)
{
int i,j,t,ans;
if (b==0)
{
x=1;y=0;
return a;
}
else
{
ans=exgcd(b,a%b);
t=x;x=y;y=t-(a/b)*y;
}
return ans;
}
int main()
{
scanf("%d%d",&a,&b);
n=exgcd(a,b);
while (x>0 || y<0) x-=b/n,y+=a/n;
while (x+b/n<=0 && y-a/n>=0) x+=b/n,y-=a/n;
printf("%d\n%d %d\n",n,-x,y);
return 0;
}