# 欧几里得及扩展欧几里得算法【学习笔记】【数学】【同余】

## 二、扩展欧几里得（exgcd）

$$a\%b=a-b\left\lfloor\frac ab\right\rfloor$$

$$ax+by=bx’+(a-b\left\lfloor\frac ab\right\rfloor)y’\ ax+by=bx’+ay’-b\left\lfloor\frac ab\right\rfloor y’$$

$$a(x-y’)-b(x’-y-\left\lfloor\frac ab\right\rfloor y’)=0$$

$$x=y’,y=x’-\left\lfloor\frac ab\right\rfloor y’$$

## 三、方程的通解

$$\left\{\begin{matrix} x=\frac cd x_0+k \frac bd,\\ y=\frac cd y_0-k \frac ad \end{matrix}\right.,k\in \mathbb{Z}$$

## 四、同余方程，出来挨打！

### 输入输出样例

3 10


7


### 说明

$$\left\{\begin{matrix} x=x_0+kb,\\ y=y_0-ka \end{matrix}\right.k\in \mathbb{Z}$$

### Code：

#include<cstdio>
#include<cstring>
#define ll long long
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(!b)
{
x=1;
y=0;
return a;
}
ll d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
int main()
{
ll a,b,x,y;
scanf("%lld%lld",&a,&b);
exgcd(a,b,x,y);
printf("%lld\n",(x%b+b)%b);
return 0;
}


### 7 说点什么

6 Comment threads
1 Thread replies
0 Followers

Most reacted comment
Hottest comment thread
2 Comment authors
Recent comment authors
Subscribe

[…] 我之前写过的 exgcd 学习笔记 […]

… [Trackback]

[…] Read More on to that Topic: wjyyy.top/2211.html […]

… [Trackback]

[…] Here you will find 72865 additional Info on that Topic: wjyyy.top/2211.html […]

… [Trackback]

[…] Read More here to that Topic: wjyyy.top/2211.html […]

… [Trackback]

[…] Read More Information here on that Topic: wjyyy.top/2211.html […]

/* */