逆元原理详解

素颜马尾好姑娘i 2023-07-08 09:21 21阅读 0赞

###  ###

*  逆元的定义
 *  方法一：费马小定理 / 欧拉定理
 *  经典例题

# 逆元的定义 #

逆元 (Inverse element) 就是在 mod 意义下，不能直接除以一个数，而要乘以它的逆元。

比如 a ∗ b ≡ 1 (mod p)，那么 a，b 互为模 p 意义下的逆元，比如你要算 x / a % p，就可以改成 x \* b % p 。

求逆元有很多方法，请看下面！

# 方法一：费马小定理 / 欧拉定理 #

**费马小定理：** *若 p 为素数*，则有  a p − 1 ≡ 1   ( m o d   p ) a^\{p−1\}≡1\\ (mod\\ p) ap−1≡1 (mod p)  
即  a p − 2   ∗   a ≡ 1   ( m o d   p ) a^\{p−2\}\\ ∗\\ a≡1\\ (mod\\ p) ap−2 ∗ a≡1 (mod p)  
则  a p − 2 a^\{p−2\} ap−2 就是 a 在 mod p 意义下的逆元

**欧拉定理：** *若 a、p 互素*，则有  a φ ( p ) ≡ 1 ( m o d   p ) a^\{φ(p)\}≡1(mod\\ p) aφ(p)≡1(mod p) （费马小定理的一般形式）  
得  a φ ( p ) − 1   ∗   a ≡ 1   ( m o d   p ) a^\{φ(p)-1\}\\ ∗\\ a≡1\\ (mod\\ p) aφ(p)−1 ∗ a≡1 (mod p)  
故  a φ ( p ) − 1 a^\{φ(p)-1\} aφ(p)−1 就是 a 在 mod p意义下的逆元

**性能分析：**  O ( l o g   m o d ) O(log\\ mod) O(log mod)  
适用范围：一般在 mod 是个素数的时候用，比扩展欧几里得方法快一点而且好写。

**Code：**

ll q_pow(ll a,ll b,ll mod){ 
        ll ans=1,res=a%mod;
        while(b){ 
            if(b&1)    ans=ans*res%mod;
            res=res*res%mod;
            b>>=1;
        }
        return ans%mod;
    }
    ll inv(ll a,ll mod){ 
        return q_pow(a,mod-2,mod)%mod;
    }

# 经典例题 #

**例题1：**[http://poj.org/problem?id=1845][http_poj.org_problem_id_1845]

**题意：** 给定两个正整数 A 和 B ，求  A B A^B AB 的所有因子和对9901取余后的值。

**例题2：** [https://www.lydsy.com/JudgeOnline/problem.php?id=2186][https_www.lydsy.com_JudgeOnline_problem.php_id_2186]

**题意：** 求 1 到 N! 中与 M! 互质的数的个数，其中 M <= N 。

**例题3：** [http://codeforces.com/contest/964/problem/C][http_codeforces.com_contest_964_problem_C]

**题意：**

**例题4：** [https://ac.nowcoder.com/acm/contest/3005/C][https_ac.nowcoder.com_acm_contest_3005_C]

**思路：** 这里用尺取法 + 逆元来做。l 代表左端点，r 代表右端点。l 先不动，r 往前扫描，如果成功扫到，有 k 个非0元素的子段就累乘起来，最后把最左端的元素除了（用乘法逆元，否则会出现除以 0 的异常），左端点往前移动，l++，再继续扫描。在未达到 k 个非零元素的子段前，如果遇到 0，当前的区间重置 ,左端点直接到 0 的下一个位置继续扫描。

#include <iostream>
    using namespace std;
    typedef long long ll;
    const int N=2e5+100;
    const ll mod=998244353;
    int n,k;
    ll a[N];
    ll q_pow(ll a,ll b){ 
        ll ans=1,res=a%mod;
        while(b){ 
            if(b&1)    ans=ans*res%mod;
            res=res*res%mod;
            b>>=1;
        }
        return ans%mod;
    }
    ll inv(ll a,ll mod){ 
        return q_pow(a,mod-2)%mod;
    }
    int main(){ 
        cin>>n>>k;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        int l=1,r=1;
        ll mul=1,ans=0;
        while(r<=n){ 
            if(a[r]){ 
                mul=mul*a[r]%mod;
                if(r-l+1==k){ 
                    ans=max(ans,mul);
                    mul=mul*inv(a[l],mod)%mod;
                    l++;
                }
            }
            else{ 
                mul=1;
                l=r+1;
            }
            r++;
        }
        cout<<ans<<endl;
        return 0;
    }

[http_poj.org_problem_id_1845]: http://poj.org/problem?id=1845
[https_www.lydsy.com_JudgeOnline_problem.php_id_2186]: https://www.lydsy.com/JudgeOnline/problem.php?id=2186
[http_codeforces.com_contest_964_problem_C]: http://codeforces.com/contest/964/problem/C
[https_ac.nowcoder.com_acm_contest_3005_C]: https://ac.nowcoder.com/acm/contest/3005/C