In the process of learning some knowledge points of informatics number theory, there are two more important algorithms, that is, Euclidean algorithm and extended Euclidean algorithm.
Today, we will take you to understand the two algorithms, what problems do the algorithms that look similar solve?
Euclid algorithm
Before learning an algorithm, I think we should first know what problem this algorithm is trying to solve.
The greatest common divisor of two numbers has been learned in elementary school, and the Euclidean algorithm is designed to find the greatest common divisor of two numbers a and b, which can be expressed as gcd(a,b).
Euclidean's algorithm, also known as tossional division, has revealed its main idea:
The idea of Euclid's algorithm is based on the principle of tossional division, which is the core idea of Euclid's algorithm, and Euclid's algorithm is actually the implementation of the computer algorithm of tossional division. Let's first talk about the tossing division method, the content of the tossing division method: If gcd(a,b) is used to represent the greatest common divisor of a and b, then according to the principle of tossional division, there are gcd(a,b)=gcd(b,a mod (b)), where mod() represents the modulo operation, and it is advisable to let a >b, which is convenient for the modulo operation.
引理：gcd(a,b)=gcd(b,a%b)
prove:
设 r=a%b , c=gcd(a,b)
Then a=xc, b=yc, where x, y are mutually identical
r=a%b=a-pb=xc-pyc=(x-py)c
而b=yc
Knowable: y and x-py are cross-identical
prove:
Suppose y and x-py are not mutually exclusive
Let y=nk , x-py=mk , and k>1 (because of the intermutation)
Bring y into availability
x-pnk=mk
x=(pn+m)k
则 a=xc=(pn+m)kc , b=yc=nkc
Then the greatest common divisor of a and b is kc and not k
Contradictory to the original proposition, then y and x-py are mutually homogeneous
Because y and x-py are mutually exclusive, the greatest common divisor of r and b is c
即 gcd(b,r)=c=gcd(a,b)
Certified
当a%b=0时，gcd(a,b)=b
In this way we can write it in recursive form
Its function code is only one line, simple and convenient, complexity O(log n):
code
int gcd(int a, int b)//Euclidean algorithm Time complexity: O(logn)
{
if(!b) return a;
else return gcd(b,a%b);
}
int gcd(int a, int b)//Simplified Euclidean algorithm Time complexity: O(logn)
return b?gcd(b, a%b): a;//A line of code is cool
Extend the Euclid algorithm
Used to solve a set of x and y in a and b, so that ax +by=gcd(a,b) holds (according to the correlation theorem of number theory, this set of solutions must exist).
Learn about Bezu's theorem: if a and b are integers, then there must be integers x and y, satisfying ax+by=gcd(a,b).
In other words, if ax+by=m has a solution, then m must be several times that of gcd(a,b). (You can judge whether there is a solution to such a formula)
A direct application is that if ax+by=1 has a solution, then gcd(a,b)=1;
Asking for this maximum common factor gcd(a,b), the easiest thing we can think of is the ancient and fairly powerful Euclidean algorithm:
However , for the equation ax+by=m above , we don't just want to know if there is a solution, but we want to know how much the solution is in the case of a solution.
So, expand Euclid
When the recursive boundary is reached, b==0, a=gcd(a,b) can observe a solution of this equation: a*1+b*0=gcd(a,b), x=1, y=0, note that a and b at this time are no longer the original a and b, so if we want to ask for a solution of x and y, we must return to the original appearance.
Preliminary idea: Since it is a recursive algorithm, if we know the relationship between this layer and the previous layer, we can push it down layer by layer, and we can push it to the very beginning. Similar to mathematical induction in mathematics.
Suppose that we currently have the greatest common divisor of a and b when we are looking for it, and we have already figured out the maximum common factor of the next state: b and a%b, and have solved a set of x1 and y1 such that b*x1+(a%b)*y1=gcd
(Note that in the recursive algorithm, it is always the value of the following state that is obtained first)
At this point we can try to find the relationship between these two adjacent states:
First we know: a%b = a-(a/b)*b;
b*x1 + (a-(a/b)*b)*y1
= b*x1 + a*y1 – (a/b)*b*y1
= a*y1 + b*(x1 – a/b*y1) = gcd 发现 x = y1 , y = x1 – a/b*y1
This way we get the conversion of x and y for every two adjacent states, and we can evaluate x and y at the same time as gcd.
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int exgcd(int a, int b, int &x, int &y)//extends the Euclidean algorithm
if(b==0) {
x=1;y=0;
return a; Reach the recursive boundary and begin to return to the next level
int r=exgcd(b,a%b,x,y);
int temp=y; Turn x y into the upper layer
y=x-(a/b)*y;
x=temp;
return r; Get the maximum common factor of a b
Main applications:
1. Multiplying inverse elements
For elements in the contraction system, each number a has a unique multiplicative inverse x, such that ax ≡1 (mod n)
A sufficient requirement for a number to have an inverse element is gcd(a,n) = 1, in which case the inverse element only exists
Meaning of inverse element: In the sense of modulo n, if there is an inverse x for 1 number a, then dividing by a is equivalent to multiplying by x.
Extended Euclidean solution:
Given the modulus m, the inverse of a is equivalent to solving ax=1(mod m)
This equation can be converted to ax-my=1
Then apply the method of solving binary one-time equations to obtain a set of x0, y0 and gcd using the extended Euclidean algorithm
Check if gcd is 1
A gcd of 1 indicates that the inverse element does not exist
If it is 1, it can be adjusted to the range of x0 to 0~m-1
typedef long long ll;
void extgcd(ll a,ll b,ll& d,ll& x,ll& y){
if(!b){ d=a; x=1; y=0;}
else{ extgcd(b,a%b,d,y,x); y-=x*(a/b); }
ll inverse(ll a,ll n){
ll d,x,y;
extgcd(a,n,d,x,y);
return d==1? (x+n)%n:-1;
2. Solve the linear congruence equation
Source: https://www.cnblogs.com/lr599909928/p/12704583.html
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int> PII;
typedef pair<long,long> PLL;
int exgcd(int a,int b,int &x1,int &y1){
int x2,y2;
if(b==0){
x1=1,y1=0;
return a;
int d=exgcd(b,a%b,x2,y2);
x1=y2,y1=x2-a/b*y2;
return d;
int main() {
ios::sync_with_stdio(false);
int n;
cin>>n;
while(n--){
int a,b,m;
int x1,y1;
cin>>a>>b>>m;
int d=exgcd(a,m,x1,y1);
if(b%d) printf("impossible\n");
else printf("%lld\n",(ll)x1*(b/d)%m);
return 0;
3. Solve indefinite equations
For the indefinite integer equation pa+qb=c, if c mod Gcd(p, q)=0, there is an integer solution for the equation, otherwise there is no integer solution.
The methods for finding an integer solution have been listed above, and after finding a set of solutions p0 for p * a + q * b = Gcd(p, q), p * a + q * b = Gcd(p, q) other integer solutions are satisfied:
p = p0 + b/Gcd(p, q) * t
q = q0 - a/Gcd(p, q) * t (where t is any integer)
As for the integer solution of pa +qb=c, simply multiply each solution of p * a + q * b = Gcd(p, q) on c/Gcd(p, q).
After finding a set of solutions p0, q0 of p* a + q * b = Gcd(a, b), it should be a set of solutions p1 = p0 * (c/Gcd(a,b)), q1 = q0*(c/Gcd(a,b)),
p * a + q * b = other integer solutions of c satisfy:
p = p1 + b/Gcd(a, b) * t
q = q1 - a/Gcd(a, b) * t (where t is any integer)
p and q are all integer solutions of p * a + q * b = c.
Solve the indeterminate equation ax+by=c using the extended Euclidean algorithm;
The code is as follows:
bool linear_equation(int a,int b,int c,int &x,int &y)
int d=exgcd(a,b,x,y);
if(c%d)
return false;
int k=c/d;
x*=k; y*=k; All that is sought is one of the solutions
return true;
Disclaimer: Some of the information comes from the Internet, invaded and deleted.