拓展欧几里得算法

扩展欧几里德算法的应用主要有以下三方面：

（1）求解不定方程；

（2）求解模线性方程（线性同余方程）；

（3）求解模的逆元；

递归形式：

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

非递归形式：

 1 int exgcd(int m,int n,int &x,int &y)
 2 {
 3     int x1,y1,x0,y0;
 4     x0=1; y0=0;
 5     x1=0; y1=1;
 6     x=0; y=1;
 7     int r=m%n;
 8     int q=(m-r)/n;
 9     while(r)
10     {
11         x=x0-q*x1; y=y0-q*y1;
12         x0=x1; y0=y1;
13         x1=x; y1=y;
14         m=n; n=r; r=m%n;
15         q=(m-r)/n;
16     }
17     return n;
18 }

（1）使用扩展欧几里德算法解决不定方程的办法：

对于不定整数方程pa+qb=c，若 c mod Gcd(p, q)=0,则该方程存在整数解，否则不存在整数解。
上面已经列出找一个整数解的方法，在找到p * a+q * b = Gcd(p, q)的一组解p0,q0后，p * a+q * b = Gcd(p, q)的其他整数解满足：
p = p0 + b/Gcd(p, q) * t
q = q0 - a/Gcd(p, q) * t(其中t为任意整数)
至于pa+qb=c的整数解，只需将p * a+q * b = Gcd(p, q)的每个解乘上 c/Gcd(p, q) 即可。

在找到p * a+q * b = Gcd(a, b)的一组解p0,q0后，应该是得到p * a+q * b = c的一组解p1 = p0*(c/Gcd(a,b)),q1 = q0*(c/Gcd(a,b))，

p * a+q * b = c的其他整数解满足：

p = p1 + b/Gcd(a, b) * t

q = q1 - a/Gcd(a, b) * t(其中t为任意整数)

p 、q就是p * a+q * b = c的所有整数解。

用扩展欧几里得算法解不定方程ax+by=c;

代码如下：

898B. Proper Nutrition

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int MAX_N = 1e5+9;
 4 long long  exgcd(long long  m,long long  n,long long  &x,long long  &y)
 5 {
 6     long long  x1,y1,x0,y0;
 7     x0=1; y0=0;
 8     x1=0; y1=1;
 9     x=0; y=1;
10     long long  r=m%n;
11     long long  q=(m-r)/n;
12     while(r)
13     {
14         x=x0-q*x1; y=y0-q*y1;
15         x0=x1; y0=y1;
16         x1=x; y1=y;
17         m=n; n=r; r=m%n;
18         q=(m-r)/n;
19     }
20     return n;
21 }
22 int main()
23 {
24     long long a,b,c,x,y;
25     cin>>c>>a>>b;
26     long long g = exgcd(a,b,x,y);
27     if(c%g) cout<<"NO"<<endl;
28     else{
29         
30         x*=c/g;
31         y*=c/g;
32         while(x<0) x+=b/g,y-=a/g;
33         while(y<0) y+=a/g,x-=b/g;
34         if(x<0 || y<0) 
35         {
36             cout<<"NO"<<endl;
37             return 0;
38         }
39         cout<<"YES"<<endl;
40         cout<<x<<" "<<y<<endl;
41     }
42 }