自动搬运

查看原文

来自洛谷，原作者为

	Gary818 **

搬运于2025-08-24 21:23:25，当前版本为作者最后更新于2019-06-28 20:31:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

偷偷嘟囔几句：为啥因为排版丑拒我好几次，好委屈

楼上的大佬们讲了思路和代码
我在这里简单讲下欧几里得和扩展欧几里得吧
开讲之前，先来说下必须知识

• 裴蜀（贝祖）定理

若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~）