[LGOJ1292] 倒酒

描述 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(05 3

样例输出 SampleOutput

1
1 2


LGOJ 1292


代码 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;
}