洛谷题解 P1292 【倒酒】

原题传送门

题目描述

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酒杯中剩下的酒的体积尽可能小，他请求你帮助他设计倾倒的方案

输入格式

两个整数a和b（0<b≤a≤10^9）

输出格式

第一行一个整数c，表示可以得到的酒的最小体积。

第二行两个整数Pa和Pb（中间用一个空格分隔），分别表示从体积为a ml的酒杯中倒出酒的次数和将酒倒入体积为b ml的酒杯中的次数。

若有多种可能的Pa、Pb满足要求，那么请输出Pa最小的一个。若在Pa最小的情况下，有多个Pb满足要求，请输出Pb最小的一个。

输入输出样例

输入 #1

5 3

输出 #1

1
1 2

说明/提示

样例解释：倾倒的方案为：

1、桶->B杯；2、B杯->A杯；

3、桶->B杯；4、B杯->A杯；

5、A杯->桶; 6、B杯->A杯；

------------------------------------------------以下为题解部分-----------------------------------------------

分析：

首先看完这个题，我瞬间想到了我小学时做的奥数题。。。。。。
然后我翻了翻，发现没有做错题。。。。。。

咳咳，进入正题:

这个题首先基本没有什么思路，按照以往的做法，我们模拟一下数据+自造数据找规律。

事实证明，完全是可以的。

这个题的考点就是数论（gcd，exgcd）

什么gcd，exgcd具体做法其余dalao们已经讲的很清楚了，我这个蒟蒻简单叨叨几句:

拓展欧几里得算法：

一定存在整数a,b,使得ax+by=(x,y)

欧几里得算法：gcd(x,y)->gcd(y,x%y)

gcd(x,y)->gcd(y,x-⌊x/y⌋*y)

如果已知a’y+b’(x- ⌊x/y⌋ *y)=(x,y)

整理得b’x+(a’-b’⌊x/y⌋)y=(x,y)

最底层：x’=(x,y) y’=0

显然有1x’+0y’=(x,y)

于是可以递归求出a,b

拓展欧几里得算法告诉我们x与y的线性组合的取值可以是(x,y),那么自然(x,y)的整数倍也能够被取到。/

Thm: x与y的线性组合能且仅能取(x,y)的整数倍

那线性组合又是什么？

Def:∀a,b∈Z ax+by为x与y的一个线性组合

那么x与y的线性组合可能取到哪些值？

设k=(x,y), p=ax+by

p=k(ax/k+by/k)

p是k的整数倍！

x与y的线性组合的取值只能是x与y的gcd的整数倍

话不多说，上代码：

#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<iostream>
#define LL long long    //比较懒。。。。
using namespace std;
LL exgcd(LL x,LL y,LL &a,LL &b)     //扩展欧几里得的核心算法
{
    if(y==0) {a=1;b=0;return x;}
    LL aa,bb,ans;
    ans=exgcd(y,x%y,aa,bb);
    a=bb;
    b=aa-bb*(x/y);
    return ans;
}
int main()
{
    LL a,b,pa,pb,g;
    cin>>a>>b;
    g=exgcd(a,b,pa,pb); //一轮exgcd操作
    a/=g;b/=g;
    LL t=pa/b;
    pa-=t*b;pb+=t*a;
    while(pa>0) pa-=b,pb+=a;    //处理最小值
    while(pa-b>=0) pa-=b,pb+=a;//（同上）
    cout<<g<<endl<<-pa<<' '<<pb;
    return 0;
}

巴特西