欧几里得算法：
就是辗转相除法，gcd(a,b)=gcd(b,a%b),
实现简单，用途广泛，模板如下：
int gcd(int a,int b)//或者都取 long long
{
return b!=0 ? gcd(b,a%b):a;
}
扩展欧几里得算法：
扩展欧几里得算法是欧几里得算法(又叫辗转相除法)的扩展。除了计算a、b两个整数的最大公约数，此算法还能找到整数x、y(其中一个很可能是负数)。
通常谈到最大公因子时, 我们都会提到一个非常基本的事实: 给予二整数 a 与 b, 必存在有整数 x 与 y 使得ax + by = gcd(a,b)。
有两个数a,b，对它们进行辗转相除法，可得它们的最大公约数–这是众所周知的。
然后，收集辗转相除法中产生的式子，倒回去，可以得到ax+by=gcd(a,b)的整数解。
ex_gcd(a,b,x,y)
假设a>b;
1、若b=0,则gcd(a,b)=a,得到x=1,y=0;
2、若a*b!=0
有ax1+by1=gcd(a,b);
bx2+(a%b)y2=gcd(b,a%b);
由欧几里得算法可得：gcd(a,b)=gcd(b,a%b);
即有：
ax1+by1=bx2+(a%b)y2;
即，ax1+by1=bx2+[a-(a/b)b]y2=ay2+bx2-b(a/b)y2;
由于 a和b是定值，且等式恒等，所以，
x1=y2,
y1=x2-(a/b)y2;
这样通过求解x2,y2来得到x1,y1。
代码如下：
#include<cstdio>
int exgcd(int a,int b,int &x,int &y)
{
if(!b)
{
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;
}
int main()
{
int a,b,x,y;
scanf("%d %d",&a,&b);
int c=exgcd(a,b,x,y);//最大公约数
printf("%d %d\n",c,(x+b)%b);
return 0;
}
此算法即可求出gcd(a,b)，也可求出x和y。
Zn * ={x| x>0 && x< n && gcd(x,n)=1 };
乘法逆元：对于集合Zn *中的元素，每个数a均有唯一的与之对应的乘法逆元x,使得ax≡1(mod n)。
一个数有逆元的充分必要条件是gcd(a,n)=1,此逆元唯一存在。
逆元的含义：模n意义下，1个数a如果有逆元x，那么除以a相当于乘以x。
扩展欧几里得算法求乘法逆元：
给定模数n，求a的逆相当于求解ax=1(mod n),这个方程可以转化为ax-my=1,然后套用二元一次方程的方法，用扩展欧几里得算法求得一组x0,y0和gcd;检查gcd是否为1
gcd不为1说明逆元不存在，若为1,调整x0到0~m-1的范围中即可。
代码如下：
int mod_reverse(int a,int n)//ax=1(mod n) 求a的逆元x
{
int d,x,y;
d=ex_gcd(a,n,x,y);
if(d==1)
return (x%n+n)%n;
else
return -1;
}
刚刚想起来之前写过一篇用 Python求RSA解密的博客，是19年蓝桥杯省赛的题，现在补上c++解法：
题目链接：https://blog.csdn.net/weixin_43107805/article/details/89515994
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=500000;
ll n=1001733993063167141;
ll p=891234941;
ll q=1123984201;
ll c=20190324; //密文
ll d=212353; //公钥
ll m=(p-1)*(q-1); //求 X = c^e mod (p-1)*(q-1);
ll e; // d*e≡1(mod Φ(n))
//求e 枚举不可取，会爆long long
/*void get_e( )
{
for(int i=1;i<=N;i++)
{
if( (m*i+1)%d==0)
{
cout<<"get_e="<<e<<endl;
e=(m*i+1)%d;
break;
}
}
} */
//求e 扩展欧几里得
ll ex_gcd(ll a,ll b,ll &x,ll &y)//扩展欧几里得
{
if(b==0)
{
x=1;
y=0;
return a;
}
int r=ex_gcd(b,a%b,x,y);
int t=x;
x=y;
y=t-a/b*y;
return r;
}
ll mod_reverse(ll a,ll n)//ax=1(mod n) 求a的逆元x d*e=1mod(m)
{
ll d,x,y;
d=ex_gcd(a,n,x,y);
if(d==1)
return (x%n+n)%n;
else
return -1;
}
//快速乘
ll mult_mod(ll a, ll b, ll m) // 计算 a*b mod m
{
ll res = 0;
while(b){
if(b&1) res = (res+a)%m; // cout<<"a="<<a<<endl;
a = (a*2)%m;
b >>= 1;
}
return res;
}
//快速幂
ll quick_mod(ll a,ll b,ll m)
{
ll ans=1;
a=a%m;
while(b!=0)
{
if( b&1 ) ans=mult_mod(ans,a,m)%m;//(ans*a)%m;
a=mult_mod(a,a,m)%m; //a=(a*a)%m;
b>>=1;
}
return ans;
}
int main()
{
cout<<"m="<<m<<endl;
//get_e();
e= mod_reverse(d,m);
cout<<"e="<<e<<endl;
cout<<"d="<<d<<endl;
ll x=quick_mod(c,e,m);
cout<<x<<endl; //明文
//验证
cout<< quick_mod(x,d,m) << endl;
}
首先用扩展欧几里得求乘法逆元e，（直接枚举肯定不行，会超过long long范围）；
然后求，C^e mod m 用快速幂求解，
（但是a*a%m 也会超过long long ，只好在快速幂中调用快速乘，a=mult_mod(a,a,m)%m; 计算a=(a*a)%m ）
所以就是一个题综合了扩展欧几里得求乘法逆元，快速幂，快速乘三个知识点。
详情可见：
快速幂取模(当数很大时，相乘long long也会超出的解决办法)
https://blog.csdn.net/wrf20162305/article/details/80385438
扩展欧几里得算法及求逆元：
https://blog.csdn.net/greenary/article/details/79343176
![查找算法之二分查找查找算法之二分查找[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)