summary

Extended Euclid is used to solve the relevant equations a x + b y = m ax+by=m The problem of ax+by=m

European expansion template

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;  
}  

Judgment equation a x + b y = m ax+by=m ax+by=m or a x ≡ m ( m o d   b ) ax≡m(mod\ b) ax≡m(mod   b) Is there a solution

Idea: when g c d ( a , b ) ∣ m gcd(a,b)|m When gcd(a,b) ∣ m, the equation has a solution, otherwise it has no solution

Solving equation a x + b y = m ( a x ≡ m ( m o d   b ) ) ax+by=m( ax≡m(mod\ b) ) ax+by=m(ax≡m(mod   b) Minimum positive integer solution of)

thinking
1. First judge whether the equation has a solution. If there is no solution, exit directly
2. Expand Europe, seek x, make b g = m / g c d ( a , b ) , be x = ( x % b g + b g ) % b g bg=m/gcd(a,b), then x=(x\%bg+bg)\%bg bg=m/gcd(a,b), then x=(x%bg+bg)%bg

Classic examples

Example 1. Logue P1082 congruence equation

Title Description
Find the minimum positive integer solution of the congruence equation ax ≡ 1(mod b) about x.
Input format
A line containing two positive integers a and B separated by a space.
Output format
A positive integer x0, that is, the minimum positive integer solution. The input data is guaranteed to have a solution.
sample input
3 10
sample output
7

Idea: template problem, because the problem must be solved, so a ⊥ b ( a And b mutual quality ) a ⊥ b (a and b are coprime) a ⊥ b (a and b are coprime), at this time, it can be solved by either expanding Europe or Euler's theorem
Here is Euler's theorem:
a φ ( n ) ≡ 1 ( m o d   n ) ( his in ， a And n all by just whole number ， And two person mutual quality . ) a^ φ (n) ≡ 1 (MOD \ n) (where a and N are positive integers and they are mutual prime.) a φ (n)≡1(mod   n) (where a and N are positive integers, and they are mutually prime.) Fermat's small theorem is a special form of Euler's theorem

code:
European expansion:

#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;  
}  

Euler's theorem:

#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;  
}  

Example 2. Luogu P5656 binary linear equation

Title Description
Given the indefinite equation ax+by=c
If the equation has no integer solution, output - 1.
If the equation has integer solutions and positive integer solutions, output the number of positive integer solutions, the minimum value of x in all positive integer solutions, the minimum value of y in all positive integer solutions, the maximum value of x in all positive integer solutions, and the maximum value of y in all positive integer solutions.
If the equation has an integer solution but no positive integer solution, you need to output the minimum positive integer value of x and the minimum positive integer value of y in all integer solutions.
The positive integer solution is that X and y are positive integers, and 0 is not a positive integer.
The integer solution is the solution where x and y are all integers.
The minimum positive integer value of X is the minimum value of X in all integer solutions where x is a positive integer, and y is the same.
Input format
The first line is a positive integer T, representing the number of data groups.
Next, line T, three positive integers a,b,c separated by spaces.
Output format
Line T.
If the query corresponding to this line has no integer solution, a number - 1.
If the query corresponding to this line has an integer solution but no positive integer solution, it contains two numbers separated by spaces, representing the minimum positive integer value of x and the minimum positive integer value of y in the integer solution in turn.
Otherwise, it contains 5 numbers separated by spaces, which in turn represent the number of positive integer solutions. In the positive integer solution, the minimum value of x, the minimum value of y, the maximum value of x and the maximum value of y.
sample input
7
2 11 100
3 18 6
192 608 17
19 2 60817
11 45 14
19 19 810
98 76 5432
sample output
4 6 2 39 8
2 1
-1
1600 1 18 3199 30399
34 3
-1
2 12 7 50 56

code:

#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;//If the minimum positive integer solution is the minimum integer solution, do not use - 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;  
}