Skip to content

14061: 【原4061】天天爱女友

题目

题目描述

author: AimAlex 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4061

Description

天天的女朋友喜欢喝啤酒,但是酒量不行,喝多了之后就容易摔倒。有一日天天又看到女朋友去喝酒,他连忙前去制止,但他的女朋友坚持要喝酒,于是……

天天的女朋友拿出两个杯子,容积分别为a ml和b ml(0 < b ≤ a),并买了一个装满啤酒的容积无限大的酒桶,她规定天天只能做三种操作:

①将酒桶中的酒倒入容积为b ml的酒杯中;

②将容积为a ml的酒杯中的酒倒入酒桶;

③将容积为b ml的酒杯中的酒倒入容积为a ml的酒杯中。

并且每次倒酒必须把杯子倒满或者把被倾倒的杯子倒空。 天天可以进行任意次操作,然后他的女朋友只会喝下容积为a ml酒杯中剩下的酒(注意:她的女朋友不希望得到一个空杯子)。

天天很听女朋友的话,但是为了不让女朋友摔倒,他希望能够通过尽量少的操作使得女朋友喝的酒最少(即:使容积为a ml的酒杯中的酒最少,但不能为0)。请你帮助天天设计出合适的方案。

Input Format

一行,两个空格隔开的整数a,b (0 < b ≤ a)。

对于30%的数据,b整除a; 对于50%的数据,a < 1000; 对于100%的数据,a < 1000000000;

Output Format

第一行一个正整数c(c > 0),表示天天的女朋友喝到酒的最小体积。(由于天天的女朋友一定要喝酒,所以c不能为0)

第二行两个整数m和n(中间用一个空格分隔),分别表示从体积为a ml的酒杯中倒出酒(即操作②)的次数和将酒倒入体积为b ml的酒杯中(即操作①)的次数。 会有多组可能的m、n满足要求,请输出m最小的一个。若在m最小的情况下,有多个n满足要求,请输出n最小的一个。

Sample Input

4 2

Sample Output

2
    0 1

zqy2018's solution

/*
    Hint: use extgcd
*/
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int a, b;
int exgcd(int a, int b, int &x, int &y) {
    if (b == 0){
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}
void init(){
    a = read(), b = read();
}
void solve(){
    int x, y, xx, yy;
    int d = exgcd(a, b, x, y);
    if (x > 0) x -= b / d, y += a / d;
    printf("%d\n%d %d\n", d, -x, y);
}
int main(){
    init();
    solve();
    return 0;
}