『数论』乘法逆元

在求解除法取模问题 $(a/b)\%m$ 时,我们可以转化为 $(a\%(b×m))/b$ ,

但是如果 $b$ 很大,则会出现爆精度问题,所以我们避免使用除法直接计算。

可以使用逆元将除法转换为乘法:假设 $b$ 存在乘法逆元,即与 $m$ 互质(充要条件)。

设 $c$ 是 $b$ 的逆元,即 $b×c≡1(mod~m)$

那么有 $a/b=(a/b)×1=(a/b)×b×c=a×c(mod~m)$

 

即,除以一个数取模等于乘以这个数的逆元取模

  • 逆元求解一般利用扩欧。
  • 当 $m$ 为质数的时候直接使用费马小定理, $m$ 非质数使用欧拉函数。

  • 当 $m$ 为质数的时候,神奇的线性方法。

 

扩展欧几里得算法

要求 $a,m$ 互素,存在唯一解。

int extgcd(int a, int b, int& x, int& y)
{
    int d = a;
    if(b != 0)
    {
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    }
    else
    {
        x = 1;
        y = 0;
    }
    return d;
}
int mod_inverse(int a, int m)
{
    int x, y;
    extgcd(a, m, x, y);
    return (m + x % m) % m;
}

 

费马小定理

在 $p$ 是素数的情况下,对任意整数 $x$ 都有 $x^p≡x(mod~p)$ 。

如果 $x$ 无法被 $p$ 整除,则有 $x^{p−1}≡1(mod~p)$ 。

可以在 $p$ 为素数的情况下求出一个数的逆元, $x×x^{p−2}≡1(mod~p)$ , $x^{p−2}$ 即为 $x$ 的逆元。

ll mult(ll a,ll n)  //求a^n%mod
{
    ll s=1;
    while(n)
    {
        if(n&1)s=s*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return s;
} //mult(a,n-2);

 

欧拉函数

令 $ϕ(m)$ 表示小于等于 $m$ 且与 $m$ 互素的正整数的个数。

如果 $x$ 和 $m$ 互质,则有 $x^{ϕ(m)}≡1(mod~m)$,即 $x×x^{ϕ(m)−1}≡1(mod~m)$ ,$x^{ϕ(m)−1}$ 为 $x$ 的逆元。

在 $m$ 为质数的情况下, $ϕ(m)=m−1$ ,即为费马小定理。

 

思路:

求出欧拉函数的值,利用欧拉函数的积性性质

对于任意整数 $n$ ,可以将它分解 $n=p_1^{k1}×p_2^{k2}×p_3^{k3}...p_m^{km}$ ,其中 $p_i$ 为质数, $ϕ(n)=ϕ(p_1^{k1})×ϕ(p_2^{k2})...ϕ(p_m^{km})$ 。

最后转化为 $ϕ(n)=n×\prod(p_i−1)/p_i$

对给定 $n$ 进行整数分解,时间复杂度 $O(n)$ 。

int eurler_phi(int n)
{
    int res = n;
    for(int i = 2; i * i <= n; i++)
    {
        if(n % i == 0)
        {
            res = res / i * (i - 1);
            while(n % i == 0) n /= i;
        }
    }
    if(n != 1) res = res / n * (n - 1);
    return res;
}

 

埃氏筛法求欧拉函数值的表,每次发现质因子就把他的倍数的欧拉函数乘上 $(p−1)×p$ 。

当 $n$ 为奇数时,有 $ϕ(2n)=ϕ(n)$

因为 $2n$ 是偶数,偶数与偶数一定不互素,所以只考虑 $2n$ 与小于它的奇数互素的情况,则恰好就等于 $n$ 的欧拉函数值。

int euler[maxn];
void euler_phi2()
{
    for(int i = 0; i < maxn; i++)  euler[i] = i;
    for(int i = 2; i < maxn; ++i)
    {
        if(euler[i] == i)
        {
            for(int j = i; j < maxn; j += i)
            {
                euler[j] = euler[j] / i * (i - 1);
            }
        }
    }
}

 

线性时间求所有逆元

规定 $p$ 为质数,且 $1^{−1}≡1(mod~p)$

设 $p=k×a+b,(b<a,1<a<p)$ ,即 $k×a+b≡0(mod~p)$

两边同时乘以 $a^{−1}×b^{−1}$ ,得到

$k×b^{−1}+a^{−1}≡0(mod~p)$

$a^{−1}≡−k×b^{−1}(mod~p)$

$a^{−1}≡−p/a×(p\%a)^{−1}(mod~p)$

从头开始扫一遍即可,时间复杂度 $O(n)$ 。

int inv[maxn];
inv[1] = 1;
for(int i = 2; i < maxn; i++)
    inv[i] = (p - p / i) % p * inv[p % i];

  • 44 只已被捕捉
    • Pingback: 乘法逆元数论篇【易懂教学】 – Dreame的博客

    • 伴梦人 Chrome | 59.0.3071.115 Windows 10

      来了就要留下点什么,想了想给你好多赞吧

      • 千千 Chrome | 60.0.3107.4 Windows 10

        hahah,谢谢~(/ω\*)……… (/ω•\*)

    • 凯哥自媒体 百度浏览器 | 8.4 Windows 7

      我会很多数学方面的例如老师教的加法

      • 千千 Mozilla FireFox | 52.0 Windows 10

        我也会

    • 胡杨 搜狗浏览器 Windows 7

      以前上学时我数学也是很好的

      • 千千 Edge | 15.14965 Windows 10

        以前我也是

    • SiyoChen 猎豹安全浏览器 Windows 7

      .......................这是数学么。。我数学最最最不好了

      • 千千 Edge | 15.14965 Windows 10

        数论里面的