扩展欧几里德和贝祖定理

概述

扩展欧几里德用来求解有关方程\(ax+by=m\)的问题

---

扩欧模板

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

判断方程\(ax+by=m\)或\(ax≡m(mod\ b)\)是否有解

思路:当\(gcd(a,b)|m\)时 方程有解，反之则无解

求解方程\(ax+by=m( ax≡m(mod\ b) )\)的最小正整数解

思路

1.首先判断方程是否有解，无解则直接退出

2.扩欧求\(x\)，令\(bg=m/gcd(a,b),则x=(x\%bg+bg)\%bg\)

---

例1.洛谷 P1082 同余方程

题目描述

求关于x的同余方程ax≡1(mod b)的最小正整数解。

输入格式

一行，包含两个正整数a,b,用一个空格隔开。

输出格式

一个正整数x0，即最小正整数解。输入数据保证一定有解。

输入样例

3 10

输出样例

7

题解

模板题，由于题目规定一定有解，因此\(a⊥b（a与b互质）\) ，此时既可以用扩欧求解，也可用欧拉定理求解

在这科普一下欧拉定理：

\(a^φ(n) ≡1(mod\ n)(其中，a与n均为正整数，且两者互质。)\) 费马小定理为欧拉定理的特殊形式

代码

扩欧版

#include<bits/stdc++.h>  
using namespace std;  
#define int long long  
int exgcd(int a,int b,int &x,int &y)  
{  
    if(b==0)  
    {  
        x=1;  
        y=0;  
        return a;  
    }  
    int ans=exgcd(b,a%b,x,y);  
    int tmp=x;  
    x=y;  
    y=tmp-(a/b)*y;  
    return ans;  
}  
signed main()  
{  
    int a,b;  
    int x,y;  
    cin>>a>>b;  
    exgcd(a,b,x,y);  
    x=(x%b+b)%b;  
    cout<<x<<endl;  
    return 0;  
}  

欧拉定理版

#include<bits/stdc++.h>  
using namespace std;  
#define int long long  
int qpow(int a,int n,int b)  
{  
    int ans=1;  
    while(n)  
    {  
        if(n&1) ans=ans%b*a%b;  
        a=a%b*a%b;  
        n>>=1;  
    }  
    return ans;  
}  
int euler(int n)  
{  
    int ans=n;  
    for(int i=2;i*i<=n;i++)  
    {  
        if(n%i==0) ans-=ans/i;  
        while(n%i==0) n/=i;  
    }  
    if(n>1) ans-=ans/n;  
    return ans;  
}  
signed main()  
{  
    int a,b;  
    cin>>a>>b;  
    cout<<qpow(a,euler(b)-1,b)<<endl;  
    return 0;  
}  

---

例2.洛谷P5656 二元一次方程

题目描述

给定不定方程ax+by=c 若该方程无整数解，输出-1。 若该方程有整数解，且有正整数解，则输出其正整数解的数量，所有正整数解中x的最小值，所有正整数解中y的最小值，所有正整数解中x的最大值，以及所有正整数解中y 的最大值。 若方程有整数解，但没有正整数解，你需要输出所有整数解中x的最小正整数值，y的最小正整数值。 正整数解即为 x, y 均为正整数的解， 0 不是正整数。 整数解即为 x,y 均为整数的解。 x的最小正整数值即所有x为正整数的整数解中x的最小值，y同理。

输入格式 第一行一个正整数 T，代表数据组数。

接下来 T 行，每行三个由空格隔开的正整数a,b,c。

输出格式 T 行。

若该行对应的询问无整数解，一个数字 -1。

若该行对应的询问有整数解但无正整数解，包含 2个由空格隔开的数字，依次代表整数解中，x的最小正整数值，y 的最小正整数值。

否则包含5个由空格隔开的数字，依次代表正整数解的数量，正整数解中，x的最小值，y的最小值，x的最大值，y的最大值。

输入样例

7
2 11 100
3 18 6
192 608 17
19 2 60817
11 45 14
19 19 810
98 76 5432

输出样例

4 6 2 39 8
2 1
-1
1600 1 18 3199 30399
34 3
-1
2 12 7 50 56

代码

#include<bits/stdc++.h>  
using namespace std;  
#define int long long  
int exgcd(int a,int b,int &x,int &y)  
{  
    if(b==0)  
    {  
        x=1;  
        y=0;  
        return a;  
    }  
    int ans=exgcd(b,a%b,x,y);  
    int tmp=x;  
    x=y;  
    y=tmp-(a/b)*y;  
    return ans;  
}  
signed main()  
{  
    int t,a,b,c;  
    int x,y;  
    int minx,miny;  
    int maxx,maxy;  
    int cnt=1;  
    scanf("%lld",&t);  
    bool flag=false;  
    while(t--)  
    {  
        flag=false;  
        cnt=0;  
        scanf("%lld %lld %lld",&a,&b,&c);  
        int gcd=exgcd(a,b,x,y);  
        if(c%gcd)  
        {  
            cout<<"-1"<<endl;  
            continue;  
        }  
        int bg=b/gcd;  
        int cg=c/gcd;  
        int ag=a/gcd;  
        int tmp;  
        x*=cg;  
        y*=cg;  
        //cout<<"x= "<<x<<"y="<<y<<endl;  
        tmp=x;  
        x=(x%bg+bg-1)%bg+1;//最小正整数解  若是最小整数解则不用-1  
        int ansy=(y%ag+ag-1)%ag+1;  
        int t=(x-tmp)/bg;  
        y-=t*ag;  
        if(x>0&&y>0)  
        {  
            minx=x;  
            maxy=y;  
            flag=true;  
            cnt=1;  
            int k=y/ag;  
            if(y%ag==0)  
            {  
                cnt+=k-1;  
                miny=ag;  
                maxx=x+(k-1)*bg;  
            }  
            else  
            {  
                cnt+=k;  
                miny=y-k*ag;  
                maxx=x+k*bg;  
            }  
        }  
        if(flag) printf("%lld %lld %lld %lld %lld\n",cnt,minx,miny,maxx,maxy);  
        else printf("%lld %lld\n",x,ansy);  
    }  
    return 0;  
}