一、首先我们要先知道扩展欧几里得原理（ax+by=gcd(a,b)）其实并没有要求a与b必须互质，a与b互质只是他的一种情况，在下面我将讲解一个a与b互质与不互质的题目。。。。。。不多说先看原理！
即如果a、b是整数，那么一定存在整数x、y使得ax+by=gcd(a,b)。
换句话说，如果ax+by=m有解，那么m一定是gcd(a,b)的若干倍。（可以来判断一个这样的式子有没有解）
有一个直接的应用就是 如果ax+by=1有解，那么gcd(a,b)=1；
要求出这个最大公因数gcd(a,b)，我们最容易想到的就是古老悠久而又相当强大的辗转相除法：
int gcd(int a,int b){ return b==0?a:gcd(b,a%b);}
但是，对于上面的式子ax+by=m来说，我们并不仅仅想要知道有没有解，而是想要知道在有解的情况下这个解到底是多少。
所以，扩展欧几里得
当到达递归边界的时候，b==0，a=gcd(a,b) 这时可以观察出来这个式子的一个解：a*1+b*0=gcd(a,b)，x=1,y=0，注意这时的a和b已经不是最开始的那个a和b了，所以我们如果想要求出解x和y，就要回到最开始的模样。
初步想法：由于是递归的算法，如果我们知道了这一层和上一层的关系，一层一层推下去，就可以推到最开始的。类似数学上的数学归纳法。
假设当前我们在求的时a和b的最大公约数，而我们已经求出了下一个状态：b和a%b的最大公因数，并且求出了一组x1和y1使得 b*x1+(a%b)*y1=gcd
（注意在递归算法中，永远都是先得到下面一个状态的值）
这时我们可以试着去寻找这两个相邻状态的关系：
首先我们知道：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
原文：https://blog.csdn.net/destiny1507/article/details/81750874
代码：
#include <iostream> #include <stdio.h> #include <stdlib.h> #include <ctype.h> #include<string.h> #include <math.h> #include<algorithm> using namespace std; 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); } } int ModularInverse(int a,int b) { ll d,x,y; extgcd(a,b,d,x,y); return d==1?(x+b)%b:-1; //返回的结果就是(1/a)mod(b)的结果 // complete this part } int main() { printf("%d\n",ModularInverse(2,3));//结果是2 /* 2*x+3*y=1mod(3) //那个x就是(1/2)mod(3)的结果，y的话不用管，因为3*y取模于3都是0 */ return 0; }
二、题目（不互质）
1、
两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。
我们把这两只青蛙分别叫做青蛙A和青蛙B，并且规定纬度线上东经0度处为原点，由东往西为正方向，单位长度1米，这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。
Input
我们把这两只青蛙分别叫做青蛙A和青蛙B，并且规定纬度线上东经0度处为原点，由东往西为正方向，单位长度1米，这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。
输入只包括一行5个整数x，y，m，n，L，其中x≠y < 2000000000，0 < m、n < 2000000000，0 < L < 2100000000。
Output
输出碰面所需要的跳跃次数，如果永远不可能碰面则输出一行"Impossible"
Sample Input
1 2 3 4 5Sample Output
4
这一道题目的关系其实很好推出来 (x+mt)%L=(y+nt)%L 或者是 (x+mt)-(y+nt)=y-x;
(n-m)t+kL=x-y
此时这可以看作一个ax+by=c的方程 其中a=n-m,b=k,c=x-y
按照扩展欧几里得原理ax+by=gcd(a,b),但是现在的c并不是，但是我们可以将ax+by=gcd(a,b)《一式》化成ax+by=c《二式》的形式
可以将一式左右都乘与c/gcd(a,b),这样我们可以得到啊a`x+b`y=c
这样就可以带入扩展欧几里得公式中从而得到一组解
但是此时得到的x0和y0并不是原式的，这个解是我们将原式乘与c/gcd(a,b)而得到的，所以我们想要得到原式的解，我们可以利用a`x0=ax且a`=a*(c/gcd(a,b))
易知x=c/gcd(a,b)*x0
y0=c/gcd(a,b)*y0
但是这并不是题目上要的最后结果，题目上要的是最小值，我们只是得到了一组解，这是一个二元函数，是一条直线，所以有多个解，既然是一条直线，x和y就满足一个参数方程
即
x = x0 + (b/gcd)*k
y = y0 - (a/gcd)*k 将这两个带入方程就是看到x0和y0后面的刚好消掉
在本题我们要求x0，我们已知的是x，所以对(b/gcd)取模，判断是否小于0，如果是就+=(b/gcd)（可以上代码了“——”）
1 #include<stdio.h> 2 #include<string.h> 3 typedef long long ll; 4 long long gcd(long long a,long long b,long long &x,long long &y) 5 { 6 //这种方法求出来的不是最小值，而是一个通解 7 //x=x0+gcd(a,b)*k; 8 //y=y0+gcd(a,b)*k; 9 if(b==0) 10 { 11 x=1; 12 y=0; 13 return a; 14 } 15 long long r=gcd(b,a%b,x,y); long long t=x; 16 x=y; 17 y=t-(a/b)*y; 18 return r; 19 } 20 //ll gcd(ll a,ll b,ll &x,ll &y) 21 // 22 //{ 23 // 24 // ll r,t; 25 // 26 // if(!b) 27 // 28 // { 29 // 30 // x=1; 31 // 32 // y=0; 33 // 34 // return a; 35 // 36 // } 37 // 38 // r=gcd(b,a%b,x,y); 39 // 40 // t=x; 41 // 42 // x=y; 43 // 44 // y=t-a/b*y; 45 // 46 // return r; 47 // 48 //} 49 int main() 50 { 51 long long a,f,g,x,y,m,n,l; 52 scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l); 53 g=x-y; 54 a=gcd(n-m,l,x,y); 55 if(g%a==0) 56 { 57 x=(g/a)*x; 58 f=l/a; 59 //y=c/a*d; 60 // if(x>=0) 61 // x=x% 62 // x=(x%a+a)%a; 63 if(x<0) 64 x=(x%f+f)%f; 65 else x%=f; 66 printf("%lld\n",x); 67 } 68 else printf("Impossible\n"); 69 return 0; 70 }
2、（互质）
给出2个数M和N(M < N)，且M与N互质，找出一个数K满足0 < K < N且K * M % N = 1，如果有多个满足条件的，输出最小的。
Input输入2个数M, N中间用空格分隔（1 <= M < N <= 10^9)Output输出一个数K，满足0 < K < N且K * M % N = 1，如果有多个满足条件的，输出最小的。Sample Input
2 3
Sample Output
2
很容易得到关系式k*m*x+n*y=1; a=k*m,b=n
gcd(a,b)=1, 但他们互质的时候题目变得不那么复杂，不用将ax+by=c 化成ax+by=gcd(a,b)
这样就可以直接把他们带入到欧几里得公式中
为了防止最后x为负值，我们就要不断加上n
为什么加n呢。。
x = x0 + (b/gcd)*k
y = y0 - (a/gcd)*k
此时gcd=1；x就是不断加上b，b就是n
贴代码：
1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 using namespace std; 5 typedef long long ll; 6 ll m,n,k; 7 void gcd(ll a,ll b,ll &x,ll &y) 8 { 9 if(b==0) 10 { 11 x=1; 12 y=0; 13 return; 14 } 15 gcd(b,a%b,x,y); 16 int t=x; 17 x=y; 18 y=t-(a/b)*y; 19 } 20 int main() 21 { 22 int i,j,k; 23 ll x,y; 24 scanf("%lld%lld",&m,&n); 25 gcd(m,n,x,y); 26 while(x<0) 27 { 28 x+=n; 29 } 30 printf("%d\n",x); 31 return 0; 32 }