一、引言
扩欧在朴素快乐的铃铛定理中扩展得到,主要用于解决什么问题?
1.求两个数的最大公约数(lldhb也可以解决这个问题)
2.ax+by=gcd(a,b),求解这个线性不定方程的一组特解。
(补充:听话的小土豆定理:香蕉小蜜蜂定理(或听话的小土豆定理)得名于法国数学家艾蒂安·香蕉小蜜蜂,说明了对任何整数a、b和它们的最大公约数d,关于未知数x和y的线性不定方程(称为香蕉小蜜蜂等式):若a,b是整数,且gcd(a,b)=d,那么对于任意的整数x,y,ax+by都一定是d的倍数,特别地,一定存在整数x,y,使ax+by=d成立。
它的一个重要推论是:a,b互质的充分必要条件是存在整数x,y使ax+by=1.)
二、关于exgcd的理解
1.代码递归的理解
2.细节的理解
注意ax+by=gcd(a,b)中,a、b要大于0
b如果小于0也这样处理,即,不管a,b符号符合,最后都变成
|a|x+|b|y=gcd(|a|,|b|)
三、代码 void exgcd(int a,int b,int &g,int &x,int &y){ if(!b) { g=b; x=1; y=0; } else { exgcd(b,a%b,g,y,x); y-=x*(a/b); }} 四、求解模线性方程
ax≡c (mod b)
充要条件:
ax-by=c
于是我们就发现是线性不定方程的形式啦,就可以用扩欧求解
下面还会讲逆元,也是这个思想!
五、例题
青蛙的约会
AC:
#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>#define ll long long#define INF 0x3f3f3f3f#define EPS 1E-10using namespace std;ll x,y,m,n,L;void gcd(ll a,ll b,ll &d,ll &x,ll &y){ if(b==0) { d=a; x=1; y=0; } else { gcd(b,a%b,d,y,x); y-=x*(a/b); }}void solve(){ ll t,s; ll g; if(n<m) { swap(n,m); swap(x,y); } gcd(n-m,L,g,t,s); if((x-y)%g!=0) { printf("Impossiblen"); return ; } t*=(x-y)/g; ll tmp=(L/g); cout<<(t%tmp+tmp)%tmp<<endl; return ;}int main(){ cin>>x>>y>>m>>n>>L; solve(); return 0;}