欧几里得算法求gcd(a,b)

#include<stdio.h> #include<iostream> #include<algorithm> #define MAXN_ROW 100 #define MAXN_COL 100 using namespace std; int gcd(int a, int b) //原理 gcd(a,b)=gcd(b,a%b)  { 
    //a,b大小不用考虑 如果a<b 经过以此b,a%b变换后就换回来了 return b == 0 ? a : gcd(b, a % b); //递归写法 } int gcd1(int a, int b) //原理同上 { 
    //大小也不用考虑 while (b) //非递归写法 { 
    int t; t = a; a = b; b = t % a; } return a; } int t; int main() { 
    int a, b; while (scanf("%d%d", &a, &b) != EOF) { 
    printf("%d\n", gcd1(a, b)); } return 0; } 

贝祖定理

讯享网

扩展欧几里得定理求解ax+by=gcd(a,b)

讯享网#include<stdio.h> #include<iostream> #include<algorithm> #define MAXN_ROW 100 #define MAXN_COL 100 using namespace std; int gcd(int a, int b) //原理 gcd(a,b)=gcd(b,a%b)  { 
    //a,b大小不用考虑 如果a<b 经过以此b,a%b变换后就换回来了 return b == 0 ? a : gcd(b, a % b); //递归写法 } int gcd1(int a, int b) //原理同上 { 
    //大小也不用考虑 while (b) //非递归写法 { 
    int t; t = a; a = b; b = t % a; } return a; } int exgcd1(int a, int b, int& x, int& y) //不用考虑a,b大小关系，求解方程ax+by=gcd(a,b) { 
    //如果求解的是方程ax+by=k*gcd(a,b),则b=0时退出的时候应该x=k if (!b) //引用写法 { 
    x = 1; y = 0; return a; } int ans = exgcd1(b, a % b, x, y); //执行完后x=x',y=y' 需要x=y' y=x'-[a/b]y' int temp = x; x = y; y = temp - a / b * y; return ans; } int exgcd2(int a, int b, int& x, int& y) //不用考虑a,b大小关系，求解方程ax+by=gcd(a,b) { 
    //如果求解的是方程ax+by=k*gcd(a,b),则b=0时退出的时候应该x=k if (!b) //引用写法 { 
    x = 1; y = 0; return a; } int ans = exgcd2(b, a % b, y, x); //执行完后x=y',y=x' 需要x=y' y=x'-[a/b]y' y -= a / b * x; //这部分比exgcd1来的简洁 return ans; } int exgcd3(int a, int b, int* x, int* y) //不用考虑a,b大小关系，求解方程ax+by=gcd(a,b) { 
    //如果求解的是方程ax+by=k*gcd(a,b),则b=0时退出的时候应该x=k if (!b) //指针写法 { 
    *x = 1; *y = 0; return a; } int ans = exgcd3(b, a % b, y, x); //执行完后x=y',y=x' 需要x=y' y=x'-[a/b]y' *y -= a / b * (*x); //这部分比exgcd1来的简洁 return ans; } int exgcd4(int a, int b, int& x, int& y) //非递归扩展欧几里得算法 { 
    //实质上是运用了欧几里得原理，用矩阵的形式将a,b的变换过程写出来，由欧几里得原理 //最后一定a=gcd(a,b) b=0,而前面的变换过程就对应了一个个方程，最后的方程就是要求的ax+by=gcd(a,b)的解 x = 1, y = 0; // x y a -> m n b int m = 0, n = 1; // m n b -> x-a/b*m y-a/b*n a%b int t; while (b) { 
    t = x; x = m; m = t - a / b * m; t = y; y = n; n = t - a / b * n; t = a; a = b; b = t % b; //printf("此时矩阵为\n"); //printf("%d %d %d\n", x, y, a); //printf("%d %d %d\n", m, n, b); } return a; } int t; int main() { 
    int a, b; while (scanf("%d%d", &a, &b) != EOF) { 
    int x = 0; int y = 0; printf("%d\n", exgcd4(a, b,x,y)); printf("x=%d,y=%d\n", x, y); } } 

图源：https://www.cnblogs.com/zbhfz/p/11267438.html

（通解）？

求逆元

1.根据定义 （A/B) mod m= (AK)mod m K是B的逆元
BK = 1 mod m
用费马小定理求逆元 a^(p-1)=1 mod p ，(a,p互质,p是素数)
a^(p-2)a=1mod p
所以a在mod p下的逆元是a^(p-2)
所以B在mod p下的逆元是B^(p-2)
在用mod运算性质(ab)mod p=((a mod p)(b mod p))mod p即可
2.用扩展欧几里得求逆元
求模运算中a的逆元，即解方程ax=1(mod n) 就是ax%n=1 不妨设ax/n=y,所以ax=1(mod n) 等价于方程ax=ny+1---->ax-ny=1 即解这个方程的x解，由贝祖定理 ax+by=n 如果有整数解 那么其中n一定是gcd(a,b)的倍数，所以ax-ny=1方程中,要有解，gcd(a,n)=1(把-y当成y)，所以a和n一定互质，这也是用扩展欧几里得定理，在a,n互质的条件下， 所以ax-ny=gcd(a,n)符合上述用扩展欧几里得算法求x,y的特征 我只要知道x就可以，基本上和上述代码一样。注意用扩展欧几里得求逆元求出来的x有可能是负数所以还要有x=(x%n+n)%n
3.欧拉定理求逆元？
4.O(n)求1~n逆元表？

取模运算性质：

图源其他博主