扩展欧几里得算法以及一次同余方程的几种方法

扩展欧几里得算法：

$a x + b y = g c d (a, b) $ 求出满足条件唯一的x,y的值

$设：$

a为r0，b为r1

$r_{0} = q_{1} * r_{1} + r_{2}$

$r_{1} = q_{2} * r_{2} + r_{3}$

$r_{2} = q_{3} * r_{3} + r_{4} $

$. . . . . . . . . .$

$r_{k - 1} = q_{k} * r_{k} $

其中 $r_{k} $ 就是最大公约数，现在我们可以得到 $0 * r_{k - 1} + r_{k} = g c d$ .
又因为 $r_{k} $ 可以写成 $r_{k - 1}$ 和 $r_{k - 2}$ 的代表公式即 $r_{k} = r_{k - 2} - q_{k - 1} * r_{k - 1}$ ，所以我们又能得到 $x * r_{k - 2} + r_{k - 1} = g c d$ 的 x 和 y 了

同理 $r_{k - 3} 和 r_{k - 2}$ 也可向上表示。一直向上回溯即可找到满足条件 $x * a + y * b = g c d$ 的 $x$ ， $y$

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
ll ExGcd(ll a,ll b,ll &x,ll &y)//求 a b 最大公约数，且得到gcd(a,b)=x*a+y*b;
{
    if(!b)
    {
        x=1;
        y=0;
        return a;
    }
    ll gcd=ExGcd(b,a%b,x,y);
    ll temp,k;
    k=a/b;
    temp=x;
    x=y;
    y=temp-k*y;
    return gcd;
}

利用扩展欧几里得求一次同余方程

gcd(a,m) | c ，即gcd(a,m) 是c的因子

形如式子 $a * x = c <mtext> </mtext> (m o d <mtext> </mtext> m)$ ,求满足条件的x。

且只有满足 $g c d (a, m) ∣ c$ 的时候才有解。

设 $a x_{1} + m y_{1} = g c d (a, m) <mtext> </mtext> ①$

令 $c_{1} = c / g c d (a, m)$ ,

那么等式①两边同乘以 $c_{1} $ 即可得到 $a x_{1} c_{1} + m y_{1} * c 1 = c $

即 $x = x_{1} * c_{1} = x_{1} * c / g c d (a, m) $ （ $x_{1} $ 为 $(a, m) $ 的扩展欧几里得公式中a的系数）

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
ll ExGcd(ll a,ll b,ll &x,ll &y)//求 a b 最大公约数，且得到gcd(a,b)=x*a+y*b;
{
    if(!b)
    {
        x=1;
        y=0;
        return a;
    }
    ll gcd=ExGcd(b,a%b,x,y);
    ll temp,k=a/b;
    temp=x;
    x=y;
    y=temp-k*y;
    return gcd;
}
bool IsOk;
ll calc(ll a,ll c,ll m)
{
    ll x,y;
    ll gcd=ExGcd(a,m,x,y);
    if(c%gcd!=0)
    {
        IsOk=false;
        return 0ll;
    }
    return c/gcd*x%m;
}

利用费马小定理求逆元

补充一个欧拉定理：

设φ(x)的x的欧拉函数值，如果有a和p互素，则有

$a^{φ (p)} = 1 (m o d <mtext> </mtext> p) $

费马小定理条件：a,p互素，且p是素数

则: $a^{p - 1} = 1 <mtext> </mtext> (m o d <mtext> </mtext> q) $

即: $a $ 关于 $p $ 的逆元为 $a^{p - 2} $

/* 快速幂取模即可 */

利用扩展欧几里得求逆元

前提

gcd(a,q)==1

逆元即ax+qy=1 (mod q)中的x

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
const int maxn=1e4+10;
ll ExGcd(ll a,ll b,ll &x,ll &y)//求 a b 最大公约数，且得到gcd(a,b)=x*a+y*b;
{
    if(!b)
    {
        x=1;
        y=0;
        return a;
    }
    ll gcd=ExGcd(b,a%b,x,y);
    ll temp,k;
    k=a/b;
    temp=x;
    x=y;
    y=temp-k*y;
    return gcd;
}
ll getinv(ll a,ll m)
{
    ll x,y;
    if(ExGcd(a,m,x,y)!=1)
        return -1;//不互质 不存在逆元
    return x;
}

扩展欧几里得算法 以及一次同余方程的几种方法