一些基础的关于逆元的数论


好吧其实都跟逆元有关…

扩展欧几里得(exgcd)解同余方程

问题简述

求关于 x 的同余方程 ax ≡ 1 (mod b)的最小正整数解。

实质

对数论一无所知的我一开始连式子都看不懂,然后去网上找这个式子的含义。
其实就是说
ax%b=1(a,b一定要互质,不然无解的)
​ ax=by+1
​ ax-by=1
​ ax+by=1

​ 因为a,b互质,所以
$$
ax+by=gcd(a,b)
$$
(以下部分摘自别人的博客)(https://www.zybuluo.com/samzhang/note/541890)
对于方程ax + by = gcd(a, b);我们设解为x, y

我们令a = b, b = a % b;

得到方程bx + (a % b)y = gcd(b, a % b);

由欧几里得算法可以得到gcd(a, b) = gcd(b, (a % b));

代入可得:bx +( a % b )y = gcd(a, b)

设此方程解为x1, y1;

在计算机中我们知道: a % b = a - (a / b) * b;

代入方程化解得:

ay1 + b(x1 - (a / b) y1) = gcd(a, b);

与ax + by = gcd(a, b) 联立,我们很容易得:

x = y1, y = x1- (a / b)y1

然后我们就这样可以解出来了。

明显要用递归来推这个式子的解,当b=0 时,只有x=1,y=0才能使a1+b0=gcd(a,0)

由此我们把$ax + by = 1$的其中一组解解出来了, 仅仅是其中一组解。

按着这个意思我们就可以写出exgcd的代码了!!!

1
2
3
4
5
6
7
8
9
10
11
12
13
void exgcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1;
y=0;
return ;
}
int x1,y1;
exgcd(b,a%b,x1,y1);
x=y1;
y=x1-(a/b)*y1;
}

however
这个方程的x是会解出负解的,然而我们要求的是最小正整数解,我们将如何应对!!??
从别处学到了这种操作,如下

1
printf("%d",(x+b)%b);

没错,基础地操作
原题 P1082
(一个晚上加上同学的解释才稍微搞懂了一些,然而感觉还是半懂不懂的,还要继续理解啊…..)

扩展欧几里得算法(exgcd)解不定方程

(以下部分转自解不定方程
昨天做了用扩展欧几里得做的同余方程,然后在题解的推荐下去做了P1516青蛙(蛤)的约会(+1s)
乍一看,这个题挺暴力的,退了一波式子发现其实就是解不定方程

1
2
3
4
5
6
7
(x+mt)%L=y+nt

x+mt=kL+(y+nt)//哎哟我名字是kl

x+mt-y-nt-kL=0

(m-n)t-kL=y-x

关键来了
$$
(m-n)t+kL=y-x
$$
我们把m-n看成a,L看成b,y-x看成d
就会发现其实就是要解at+bk=d
( 就是解不定方程啊)
然后就开始查资料,查如何用exgcd解类似的方程了
下面给出步骤

先给出定理:方程ax+by=c有解,当且仅当 c%gcd(a,b)=0。

  定理的证明很容易,如下:

  证明:

  若c%gcd(a,b)=0,则一定存在一个整数K,有c=K*gcd(a,b), 而我们知道ax+by=gcd(a,b)一定存在解(x1, y1),所以就有K(ax1 +by1 ) = Kgcd(a,b)——>aKx1 +bKy1 = c,得出解为:(Kx1 , Ky1 )。定理得证。

  那么在ax+by=c有解的情况下如何求解呢?

  由上可知,ax+by=c 与 ax+by=Kgcd(a,b)是等价的。另外ax+by=gcd(a,b)的一组解为 x1, y1。

  令a1=a/gcd(a,b), b1=b/gcd(a,b),c1=c/gcd(a,b).

  综上,我们可以得出x,y的一组解就是x1c1, y1c1(实际上这个解我们在上面的证明定理的过程中就可以得出这组解,只是我们要的是最小解,所以在此处给出),但是满足方程的解有无穷多个,在实际的解题中我们常常只要求其最小解。现以求x的最小解为例,至此我们已经求的一组解使得满足方程ax+by=m,那么a(x+nb)+b(y-na)=m显然也成立。可知x+nb(n=….-2,-1,0,1,2….)就是方程x解集。存在一个k使得x+kb>0,x的最小解就是(x+kb)%b.若我们将方程两边同时除以gcd(a,b),则方程变为a1x+b1y=c1,同上分析可知。x的最小值就是(x+kb1)%b1,由于b1<=b,故这个值定会小于等于之前我们认为最小值。在实际求解时常用while(x<0) x+=b来使得为正的条件满足。

  另外给出所有解得公式,若x0,y0是该方程的一组整数解,那么该方程的所有整数解可表示为

  X = x0+b/(a,b)t;

  Y = y0- a/(a,b)t;

然后给出标程

  • 其实就是在求exgcd的基础上加了一个求真gcd的函数和求最终解的操作
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    #include <bits/stdc++.h>
    using namespace std;
    long long a,b,x,y,d;
    long long e,r,m,n,l;
    void exgcd(long long a,long long b,long long &x,long long &y)
    {
    if(b==0)
    {
    x=1;
    y=0;
    return ;
    }
    long long x1,y1;
    exgcd(b,a%b,x1,y1);
    x=y1;
    y=x1-(a/b)*y1;
    }
    long long gcd(long long x,long long y)
    {
    if(y==0)return x;
    return gcd(y,x%y);
    }
    int main()
    {
    scanf("%lld %lld %lld %lld %lld",&e,&r,&m,&n,&l);
    a=m-n,b=l,d=r-e;
    long long c=gcd(a,b);
    if(d%c!=0)printf("Impossible");
    else
    {
    exgcd(a,b,x,y);
    x=x*(d/c);
    printf("%lld",(x+abs(b/c))%abs(b/c));//因为求得的gcd可能为负数,所以在b/gcd的时候要加abs,然后这一步的操作和之前求同余方程的最后一步类似,就是避免解出来的x是负解,往后再找一个通解就是最终的解了
    }
    return 0;
    }

快速幂+快速乘法

特别实用的两个函数,而且如果题目要求取模,两个函数都可以以高效率和不超long long的特点运行
很好理解吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
ll mul(ll x,ll y)
{
ll sum=0;
while(y)
{
if(y%2){sum=(sum+x)%p;}
x=(x+x)%p;
y/=2;
}
return sum;
}
ll ksm(ll x,ll y)
{
ll sum=1;
while(y)
{
if(y%2){sum=mul(sum,x);}
x=mul(x,x);
y/=2;
}
return sum;
}

费马小定理求乘法逆元

之前学过地exgcd也可以解决求逆元的问题,不过我觉得费马小来得更简单(不是定理本身…而是写法上)
这个东西其实一直知道,就是一直没有写一篇博客,考试的时候其实自己用的也不是很多,要不就是做到的要用到逆元的题看不出来,要不就是写高精模和高精除去了(然而没有一次能写清楚)

以下是费马小定理的基本内容
$$
a^{p-1}\equiv1\pmod{p}
$$

其中a、p互质

对于乘法逆元,我们知道(A/B)%M=(A∗(1/B))%M。令1/B等于H,那么H就是B关于M的乘法逆元,其实就是B关于M的一个相反数,B∗H≡1 (mod M)

将两式联立,不难发现,

$$
H=B^{p-2}
$$

然后快速幂解决就行了,甚至不需要粘代码