「ACM笔记」我对逆元的理解

本文旨在记录逆元的部分用法与简单原因,不涉及具体证明。

 一、逆元是什么?

在数论领域中可以把一个数的倒数,如1/a,看做逆元。

详细一点,a*x  ≡ 1 (mod p),x就是a关于p的逆元

再比如,2 * 3 % 5 = 1, 2和3就互为关于5的逆元

 

二、逆元的作用?

我们知道 (a + b) % p = (a % p + b % p) % p,是对的

(a – b ) % p = (a % p – b % p) % p,是对的

(a * b) % p = (a % p * b % p) % p,也是对的

但是,(a / b) % p = (a % p / b % p) % p,就是错的,不能这样。

所以,为了分解(a / b) % p ,就引入了逆元(逆元的作用就来了)

如果a 关于 b 的逆元是 inv(a)的话,那么引入逆元之后的式子就分解为 (a / b) % p = (a * inv(b)) % p, 这样就能使用乘法取模进一步分解计算了。(不理解?没关系,去看看证明吧)

 

三、求逆元的两种方法

1、费马小定理:a^p-1 ≡1(mod p)

前提条件是,p为素数,且gcd(a, p) = 1

由定理可推出:a* a^p-2 ≡1(mod p) → a^p-2 ≡ 1/a (mod p) → a^p-2 ≡ inv(a) (mod p) → inv(a) = (a^p-2) % p

所以,求逆元就可以用代码实现了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
LL POW(LL a, LL n, LL mod){
    LL ans = 1, tmp = a;
    while(n){
        if(n % 2 == 1)  ans = (ans * tmp) % mod;
        tmp = (tmp * tmp) % mod;
        n >>= 1;
    }
    return ans;
}
 
LL INV(LL a, LL p){
    return POW(a, p-2, p);
}

 

2、扩展欧几里德:a*x + b*y = gcd(a, b)

前提条件,a和b互质,所以公式为a*x + b*y = 1

结论是:x是a关于b的逆元,相对应,y是b关于a的逆元

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
void ex_gcd(LL a, LL b, LL &x, LL &y, LL &d){
    if(!b)  d = a, x = 1, y = 0;
    else{
        ex_gcd(b, a % b, y, x, d);
        y -= x * (a / b);
    }
}
 
LL INV(LL a, LL p){ //a、p代表扩展欧几里德中的a、b。
    LL x, y, d;
    ex_gcd(a, p, x, y, d);
    return d == 1? (x % p + p) % p: -1; //返回-1表示无解
}

 

参考文章:
ACM数论之旅6—数论倒数,又称逆元(我整个人都倒了( ̄﹏ ̄))

2 Comments on “「ACM笔记」我对逆元的理解

  1. It’s appropriate time to make some plans for tthe uture and it’s time too be happy.
    I’ve read this post and if I could I desire to suggest you few interewsting thihgs or tips.
    Perhaps you could write next articles referring tto this article.
    I desire to read more things about it!

发表评论

电子邮件地址不会被公开。