题解 P1292 【倒酒】
偷偷嘟囔几句：为啥因为排版丑拒我好几次，好委屈
楼上的大佬们讲了思路和代码
我在这里简单讲下欧几里得和扩展欧几里得吧
开讲之前，先来说下必须知识
-
裴蜀（贝祖）定理
若ax+by=m有解，那么m一定是gcd(a,b)的若干倍
可以百度了解一下
在这里，暂且当做已知知识
如果你看懂了裴蜀定理
把它A掉
P4549 裴蜀定理 -
欧几里得
欧几里得是啥，能吃吗？？来自灵魂深处的发问。
嗯，真香！
欧几里得算法又称辗转相除法
简称GCD
用来求两个数的最大公约数
gcd(a,b)=gcd(b,a%b)
通常我们递归实现：inline int gcd(int a,int b){ if(b==0) return a; return gcd(b,a%b); }三目运算符：
inline int gcd(int a,int b){ return b==0?a:gcd(b,a%b); }对于上面的式子 ax+by=m
我们不仅想知道有没有解，还想知道这个解到底是多少
那么就得用到今天的主角啦 -
重点来说下扩展欧几里得
模板：gcd(int a,int b,int &x,int &y)
代码一会儿补全
先来说递归的边界情况
最后一定会递归至b==0的情况
a=gcd(a,b)
a × 1+b × 0 = gcd (a , b)
下面是当a>b>0时的证明（建议手模一遍，很简单）：
a × x1+b × y2=gcd(a,b)
b × x2+(a%b) × y2=gcd(b,a%b)
由朴素的欧几里得算法得：
∵ gcd(a,b)=gcd(b,a%b)
∴ a × x1+b × y2=b × x2+(a%b) × y2
接下来用待定系数法，将等式右边变形为：
b × (x2-(a%b) × y2) + a × y2
就有了这个等式：
a × x1+b × y2=b × (x2-(a%b) × y2) + a × y2
那么，显然，对应项系数相等：
x1 = y2
y1 = (x2-(a%b) × y2)
综合上述证明，递归的式子已经很显然了
贴板子：
inline int exgcd(int a,int b,int &x,int &y){
if(b==0){
x=1,y=0;
return a;
}
int tmp=exgcd(b,a%b,x,y);
int t=x;
x=y;
y=t-a/b*x;
return tmp;
}到这里，如果你认真的看完了，并且看懂了
尝试一下这个吧
P1082 同余方程
最后，我们来说这道题P1292 倒酒
对于第一问，因为a与b互质，如果来回倒酒，
那么酒的数量一定是a和b的公约数
又因为题目说是最小的酒量
那么自然就是最大公约数啦gcd(a,b)
那我exgcd不是白讲了？？（小声bbbbb）
看数据范围，10^9
emmmm，假如酒馆老板非常抠，a和b全是特别小的杯子
妥妥的安排你去TLE
你万般无奈的回头仔细看了exgcd
并且极不情愿的把板子粘了下来
然后第一问结束了。。。
对于第二问呢，无非就是卡一个最小次数出来
本人认为@war1111
大佬讲的非常仔细，大家可以找找他的题解阅览
最后，泥谷的优良传统：高清无码
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cstring>
using namespace std;
inline int read(){
int x=0,w=1;
char ch=getchar();
for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*w;
}
inline int exgcd(int a,int b,int &x,int &y){
if(b==0){
x=1,y=0;
return a;
}
int tmp=exgcd(b,a%b,x,y);
int t=x;
x=y;
y=t-a/b*x;
return tmp;
}
int main(){
int a,b,x,y;
a=read(),b=read();
int ans=exgcd(a,b,x,y);
cout<<ans<<'\n';
x*=-1,a*=-1;
while(x<0||y<0){
x+=b/ans*(x<0);
y-=a/ans*(x>=0);
}
cout<<x<<" "<<y;
return 0;
}希望能给初学者良好的基本知识，顺手留赞（~不要脸的逃了QAQ~）