拓展欧几里得算法既可以求出最大公约数，还可以顺带求解出使得： a*x + b*y = gcd 的通解 x 和 y
它的突出作用就是求逆元：
形如：
x%m 就是最小的逆元
拓欧模板：
int extgcd(ll a,ll b,ll& x,ll& y)
{
ll d=a;
if(b!=0)
{
d=extgcd(b,a%b,y,x);
y-=(a/b)*x;
}
else x=1,y=0;
return d;
入门题：poj1061青蛙的约会
链接：http://poj.org/problem?id=1061
代码：
#include<iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define mod 1000000007
ll x,y;
ll m,n,L;
int extgcd(ll a,ll b,ll& x,ll& y)
{
ll d=a;
if(b!=0)
{
d=extgcd(b,a%b,y,x);
y-=(a/b)*x;
}
else x=1,y=0;
return d;
}
ll solve(ll a,ll b,ll c)
{
ll gcd=extgcd(a,b,x,y);
if(c%gcd!=0)return -1;
x*=c/gcd;
b/=gcd;
if(b<0)
b=-b;
ll ans=x%b;
if(ans<0)ans+=b;
return ans;
}
int main()
{
while(cin>>x>>y>>m>>n>>L)
{
ll ans=solve(m-n,L,y-x);
if(ans==-1)cout<<"Impossible"<<endl;
else cout<<ans<<endl;
}
return 0;
}
原文：https://www.cnblogs.com/zhgyki/p/9434322.html