扩展欧几里德一系列算法

一、欧几里德算法又称辗转相除法，用于计算两个正整  a，b的最大公约数。

定理：gcd(a,b) = gcd(b,a%b) 。代码实现如下：

#include<stdio.h>
#define ll long long

ll gcd(ll m,ll n)
{
    if(n==0)
        return m;
    return gcd(n,m%n);
}
int main()
{
    ll m,n;
    ll x;
    while(scanf("%lld %lld",&m,&n)!=EOF)
    {
        x=gcd(m,n);
        printf("%lld\n",x);
    }
    return 0;
}

二、扩展欧几里德：ax+by=c

x=x0+b/gcd(a,b)*t;

y=y0+a/gcd(a,b)*t;

 

由ax+by=gcd(a,b)      gcd(a,b)=gcd(b,a%b)

• ax+by=gcd(b,a%b)=bx0+(a%b)y0       a%b=a-a/b*b

• ax+by=ay0+b*(x0-a/b*y0)

• 所以可得出：x=y0     y=x0-a/b*y0
• 扩展欧几里得最大的用法就是求x,y的最小正整数解。为了求x,y的最小正整数解首先求得是 ax+by=gcd(a,b)的解。求出的x,y乘以c/gcd(a,b)。这就是ax+by=c的解而要想求最小正整数解就要看此通解公式x=x0+b/gcd(a,b)*t.其中x0=x*c/gcd;要想求最小正整数解那么就是 x=x0+b/gcd(a,b)*t两边同时对b/gcd(a,b)取余此时在加工一下就是x=（x%(b/gcd)+(b/gcd)）%(b/gcd)。

代码如下：

#include<stdio.h>
#define ll long long
ll gcd(ll m,ll n)
{
    if(n==0)
        return m;
    return gcd(n,m%n);
}
ll exgcd(ll a,ll b,ll &x,ll &y){//求扩展欧几里得中ax+by=gcd(a,b)的解
if(!b){
x=1;
y=0;
return a;
}
ll ans=exgcd(b,a%b,x,y);
ll temp=x;
x=y;
y=temp-a/b*y;
return ans;
}
ll cal(ll a,ll b,ll c)//求扩展欧几里德最小正整数解
{
    ll x,y;
    ll gcd=exgcd(a,b,x,y);
    if(c%gcd!=0)
        return -1;
    x*=c/gcd;
    b/=gcd;
    return (x%b+b)%b;
}
int main()
{
    ll a,b;
    ll c;
    ll x,y;
    ll x0,y0;
    
    while(scanf("%lld %lld %lld",&a,&b,&c)!=EOF)
    {
        gcd1=exgcd(a,b,x,y);//此时求出来的解是ax+by=gcd(a,b)的解
        x=cal(a,b,c);
        y=(c-b*y)/a;
        printf("%lld %lld\n",x,y);
    }
    return 0;
} 

 

三.1、同余定理：

给定正整数m，a/m与b/m所得余数相同，称a、b同余。

a≡b(mod m),存在整数k，使a=b+km;

a+-*c≡b+-*c（mod m）可以转化为扩展欧几里德

代码如下：

 

 

 

四、逆元

对于正整数a和m，如果有ax≡1(mod m)，那么把这个同余方程中x的最小正整数解叫做a模m的逆元。

1、扩展欧几里德求逆元：由同余定理 ax≡1(mod m)可化为

ax=1+km    ax-km=1

可直接用扩展欧几里德求出a的逆元x

2、费马小定理求逆元（当m为素数时）：ax≡1(mod m) --> x= 

推导过程：

 

五、一元线性同余方程

 

定义：形如ax≡b(mod m),  且x是未知整数的同余式称为一元线性同余方程。

 

定理：a,b,m是整数且m>0，gcd（a，m）=d，如果d|b（‘|’的意思为整除即b%d==0）,则方程恰有d个模m不同余的解否则方程无解。

可以直接用扩展欧几里德求

ll f()
{
    //ax≡b(mod m)
    ll a,b,m;
        scanf("%lld%lld%lld",&a,&b,&m);
    ll x,y;

    ll d=exgcd(a,m,x,y);
    if(b%d)
        return -1;

    x=x*(b/d)%m;
        for(int i=0;i<d;i++)
            printf("%lld ",(x+i*m/d)%m);
}

 

 

 

 

 

六、线性同余方程组

X≡r1(mod a1)

X≡r2 (mod a2)

X≡r3 (mod a3)

………………

X≡rn (mod an)

 

X=r1+a1*x

X=r2+a2*y

a1*x-a*2y=r2-r1

由扩展欧几里得通解x=x0+a2/gcd*t

带回原式 X=r1+a1*x0+a1*a2/gcd*t

由同余定理可知X≡r1+a1*x0 (mod a1*a2/gcd)

然后再令r1=r1+a1*x0

          a1=a1*a2/gcd

可将X化为X≡r1 (mod a1)

然后再与后几项依次合并就可得出X。

ll f(){
    //ax≡b(mod m)
    ll a,b,m;
    scanf("%lld%lld%lld",&a,&b,&m);

    ll x,y;
    ll d=exgcd(a,m,x,y);

    if(b%d)
        return -1;
    x=x*(b/d)%m;
    for(int i=0;i<d;i++)
        printf("%lld ",(x+i*m/d)%m);
}

 

 

七、中国剩余定理

当线性同余方程组中的m1、m2、m3..mn两两互素时,则线性同余方程组

X≡a1(mod m1)

X≡a2 (mod m2)

X≡a3 (mod m3)

………………

X≡an (mod mn)

有模M=m1*m2*m3..*mn的唯一解。

Mi=M/mi

a1*M1*p1+a2*M2*p2+a3*M3*p3+..+an*Mn*pn就是同余方程组的解

ll China()
{
    int n;
    ll M=1,a[1005],m[1005];

    ll Mi,x0,y0,ans=0,d;
        scanf("%d",&n);

    for(int i=0;i<n;i++)
        scanf("%lld%lld",&m[i],&a[i]);

    for(int i=0;i<n;i++)
        M*=m[i];

    for(int i=0;i<n;i++)
    {
        Mi=M/m[i];
        d=exgcd(Mi,m[i],x0,y0);
        ans=(ans+Mi*x0*a[i])%M;
    }

    return (ans+M)%M;
}