拓展欧几里得 学习笔记

拓展欧几里得算法

还是数论

欧几里得算法

就是求最大公约数的辗转相除法。

数学公式

$$\gcd(a, b)= \begin{cases} \gcd(b,a\bmod b) &,b\neq 0\\ a &,b=0 \end{cases}$$

模板

int gcd(int a,int b)
{
	if(b==0) return a;
	return gcd(b,a%b);
}

然后辗转相除的复习就结束了

拓展欧几里得(exgcd)

适用问题

给定正整数 $a,b$，求出 $ax+by=\gcd(a,b)$ 的一组正整数解。

算法思路

由欧几里得算法得出 $ax+by=\gcd(a,b)=\gcd(b,a\bmod b)$，代回原式，即为：

$$bx^{\prime}+a\bmod b\times y^{\prime}=\gcd(b,a\bmod b)$$

假设我们已知上式的一组解 $x^{\prime},y^{\prime}$，可以得到：

$$\begin{aligned} ax+by=\gcd(a, b) &=b x^{\prime}+a \bmod b\times y^{\prime} \\ &=b x^{\prime}+(a-\lfloor \frac{a}{b} \rfloor \times b) y^{\prime}\\ &=a y^{\prime}+b(x^{\prime}-\lfloor \frac{a}{b}\rfloor \times y^{\prime}) \end{aligned}$$

所以

$$\begin{aligned} ax+by&=ay^{\prime}+b(x^{\prime}-\lfloor \frac{a}{b}\rfloor \times y^{\prime})\\ x&=y^{\prime}\\ y&=x^{\prime}-\frac{a}{b}\times y^{\prime} \end{aligned}$$

我们发现，当 $b=0$ 时，$a\times 1+b\times 0=a$

$$\begin{aligned} x&=1\\ y&=0 \end{aligned}$$

模板

直接递归求解即可

法一

int x,y;
int exgcd(int a,int b)
{
	if(b==0)
	{
		x=1;
		y=0;
		return a;
	}
	int g=exgcd(b,a%b);
	int t=x;
	x=y;
	y=t-a/b*y;
	return g;
}

法二

int exgcd(int a,int b,int &x,int &y)
{
	if(b==0)
	{
		x=1;
		y=0;
		return a;
	}
	int g=exgcd(b,a%b,y,x);
	y=y-a/b*x;
	return g;
}

这时，我们已经得到了一组解，下一步是求解 $ax+by=c$。

---

求解 $ax+by=c$

接下来我们需要分类讨论。

设 $g=\gcd(a,b)$。

当 $c\bmod b\neq0$ 时，无解。

否则，令 $k=\frac{c}{g}$，

则

$$ax^{\prime}k+by^{\prime}k=g\times k=c$$

得

$$\begin{cases} x=x^{\prime}k\\ y=y^{\prime}k \end{cases}$$

设 $x$ 的周期 $T=\frac{b}{g}$，则最小正整数解为 $(x\bmod T+T)\bmod T$。

---

乘法逆元

定义

已知 $a,p$，求 $ax\equiv 1\pmod{p}$ 中的 $x$，称 $x$ 为 $a$ 关于 $p$ 的逆元。

求解

直接求解 $ax+py=1$ 即可。

最终答案为 $(x\bmod p+p)\bmod p$。

模板

求解里已经说得很清楚了，没必要再放板子了。

---

费马小定理

当 $p$ 为素数时，$a$ 关于 $p$ 的逆元是 $a^{p-2}$。

证明

略

---

一些板子题

P1516 青蛙的约会

这是一道比较裸的拓欧题。

100pts

#include<bits/stdc++.h>
#define ll long long
#define int ll
using namespace std;
inline ll lread()
{
	ll s=0,w=1;
	char ch=getchar();
	while(ch<'0' || ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0' && ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
int x,y,m,n,l;
int p,q;
int exgcd(int a,int b)
{
	if(!b)
	{
		p=1;
		q=0;
		return a;
	}
	int g=exgcd(b,a%b);
	int t=p;
	p=q;
	q=t-a/b*q;
	return g;
}
signed main()
{
	x=read();y=read();m=read();n=read();l=read();
	int a=n-m,b=x-y;
	if(a<0)
	{
		a=-a;
		b=-b;
	}
	int ans=exgcd(a,l);
	if(b%ans!=0)
	{
		cout<<"Impossible"<<endl;
	}
	else
	{
		cout<<((p*(b/ans))%(l/ans)+l/ans)%(l/ans)<<endl;
	}
	return 0;
}

P3811 【模板】乘法逆元