欧几里得算法（辗转相除法）
用来求解最大公约数
1 int gcd(int a,int b){
2 return b ? gcd(b,a%b) : a;
3 }
在 #include<algorithm> 中也可以直接调用 __gcd(a,b)
拓展欧几里得算法
求解不定方程：
引理：存在 x , y 使得 gcd(a,b)=ax+b
1 typedef long long ll;
2
3 ll exgcd(ll a,ll b)
4 {
5 if(b){
6 ll r=exgcd(b,a%b);
7 ll k=x;
8 x=y;
9 y=k-a/b*y;
10 return r;
11 }
12 else{
13 x=1,y=0;
14 return a;
15 }
16 }
解线性同余方程
关于 x 的模方程 ax%b=c 的解，方程转换为 ax+by=c 其中 y 一般为非正整数，则问题变为用 exgcd 解不定方程
计算乘法逆元
若 a*x≡1(mod b) ，且 a与 b互质，那么我们就能定义: x为 a的逆元
这就是利用拓欧求解线性同余方程 a*x≡c(mod b) 的 c=1 的情况。我们就可以转化为解 a*x + b*y = 1这个方程
1 typedef long long ll;
2
3 void exgcd(ll a,ll b)//扩展欧几里得算法求乘法逆元，x为a的逆元
4 {
5 if(!b){
6 x=1,y=0;
7 return;
8 }
9 exgcd(b,a%b);
10 ll k;
11 k=x;
12 x=y;
13 y=k-(a/b)*y;
14 }
一些例题
zoj 3609
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 ll gcd;
5
6 ll exgcd(ll a,ll b,ll &x,ll &y)
7 {
8 if(b==0){
9 x=1,y=0;
10 return a;
11 }
12 ll ans=exgcd(b,a%b,x,y);
13 ll temp=x;
14 x=y;
15 y=temp-a/b*y;
16 return ans;
17 }
18
19 ll cal(ll a,ll b,ll c)
20 {
21 ll x,y;
22 gcd=exgcd(a,b,x,y);
23 ll ans=(x%b+b)%b;
24 if(!ans)
25 ans=b;
26 return ans;
27 }
28
29 int main()
30 {
31 ll a,b,t;
32 cin>>t;
33 while(t--){
34 cin>>a>>b;
35 ll ans=cal(a,b,1);
36 if(gcd!=1)
37 cout<<"Not Exist\n";
38 else
39 cout<<ans<<endl;
40 }
41 return 0;
42 }
zoj 3593
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 ll x,y;
5
6 ll exgcd(int a,int b){
7 if(b){
8 ll n=exgcd(b,a%b);
9 ll xt=x;
10 x=y,y=xt-a/b*y;
11 return n;
12 }
13 x=1,y=0;
14 return a;
15 }
16
17 int main(){
18 ll n,m,t,a,b,c;
19 cin>>t;
20 while(t--){
21 cin>>n>>m>>a>>b;
22 c=n-m;
23 ll ans=exgcd(a,b);
24 if(c%ans!=0){
25 cout<<-1<<endl;
26 continue;
27 }
28 c/=ans,a/=ans,b/=ans;
29 x*=c,y*=c;
30 ll k=(y-x)/(a+b);
31 ans=10000000000ll;
32 for(ll i=k-1;i<k+2;i++){
33 ll xx;
34 ll x0=x+b*i,y0=y-a*i;
35 if(x0<=0&&y0>=0||y0<=0&&x0>=0)
36 xx=abs(x0)+abs(y0);
37 else
38 xx=max(abs(x0),abs(y0));
39 if(xx<ans)
40 ans=xx;
41 }
42 cout<<ans<<endl;
43 }
44 return 0;
45 }
poj 1061
1 #include <iostream>
2 #include <cstdio>
3 using namespace std;
4 typedef long long ll;
5 ll x,y;
6
7 ll exgcd(ll a,ll b)
8 {
9 if(b){
10 ll r=exgcd(b,a%b);
11 ll k=x;
12 x=y;
13 y=k-a/b*y;
14 return r;
15 }
16 else{
17 x=1,y=0;
18 return a;
19 }
20 }
21
22 int main()
23 {
24 ll p,q,m,n,l;
25 scanf("%lld%lld%lld%lld%lld",&p,&q,&m,&n,&l);
26 ll a=n-m,b=l,c=p-q;
27 ll ans=exgcd(a,b);
28 if(c%ans)
29 printf("Impossible\n");
30 else{
31 ll k=c/ans,t=b/ans;
32 x*=k;
33 if(t<0)
34 t=-t;
35 x=(x%t+t)%t;
36 cout<<x<<endl;
37 }
38 return 0;
39 }
hdu 1576
1 #include <iostream>
2 #include <cstdio>
3 using namespace std;
4 typedef long long ll;
5 ll x,y;
6
7 ll exgcd(ll a,ll b)
8 {
9 if(b){
10 ll r=exgcd(b,a%b);
11 ll k=x;
12 x=y;
13 y=k-a/b*y;
14 return r;
15 }
16 else{
17 x=1,y=0;
18 return a;
19 }
20 }
21
22 int main()
23 {
24 ll p,q,m,n,l;
25 scanf("%lld%lld%lld%lld%lld",&p,&q,&m,&n,&l);
26 ll a=n-m,b=l,c=p-q;
27 ll ans=exgcd(a,b);
28 if(c%ans)
29 printf("Impossible\n");
30 else{
31 ll k=c/ans,t=b/ans;
32 x*=k;
33 if(t<0)
34 t=-t;
35 x=(x%t+t)%t;
36 cout<<x<<endl;
37 }
38 return 0;
39 }