逆元详解

今天我们来探讨逆元在ACM-ICPC竞赛中的应用，逆元是一个很重要的概念，必须学会使用它。

对于正整数和，如果有，那么把这个同余方程中的最小正整数解叫做模的逆元。

逆元一般用扩展欧几里得算法来求得，如果为素数，那么还可以根据费马小定理得到逆元为。

推导过程如下

                            

求现在来看一个逆元最常见问题，求如下表达式的值（已知）

           

当然这个经典的问题有很多方法，最常见的就是扩展欧几里得，如果是素数，还可以用费马小定理。

但是你会发现费马小定理和扩展欧几里得算法求逆元是有局限性的，它们都会要求与互素。实际上我们还有一

种通用的求逆元方法，适合所有情况。公式如下

          

现在我们来证明它，已知，证明步骤如下

          

接下来来实战一下，看几个关于逆元的题目。

题目：http://poj.org/problem?id=1845

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

分析：很容易知道，先把分解得到，那么得到，那么

     的所有因子和的表达式如下

    

所以我们有两种做法。第一种做法是二分求等比数列之和。

第二种方法就是用等比数列求和公式，但是要用逆元。用如下公式即可

                     

因为可能会很大，超过int范围，所以在快速幂时要二分乘法。

其实有些题需要用到模的所有逆元，这里为奇质数。那么如果用快速幂求时间复杂度为，

如果对于一个1000000级别的素数，这样做的时间复杂度是很高了。实际上有的算法，有一个递推式如下

                   

它的推导过程如下，设，那么

       

对上式两边同时除，进一步得到

       

再把和替换掉，最终得到

       

初始化，这样就可以通过递推法求出模奇素数的所有逆元了。

另外模的所有逆元值对应中所有的数，比如，那么对应的逆元是。

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=2186

题意：求中互质的数的个数，其中。

分析：因为，所以，我们很容易知道如下结论

     对于两个正整数和，如果是的倍数，那么中与互素的数的个数为

     本结论是很好证明的，因为中与互素的个数为，又知道，所以

     结论成立。那么对于本题，答案就是

     

      其中为小于等于的所有素数，先筛选出来即可。由于最终答案对一个质数取模，所以要用逆元，这里

      求逆元就有技巧了，用刚刚介绍的递推法预处理，否则会TLE的。

代码：

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <bitset>

using namespace std;
typedef long long LL;
const int N = 10000005;

bitset<N> prime;

void isprime()
{
    prime.set();
    for(int i=2; i<N; i++)
    {
        if(prime[i])
        {
            for(int j=i+i; j<N; j+=i)
                prime[j] = false;
        }
    }
}

LL ans1[N],ans2[N];
LL inv[N];

int main()
{
    isprime();
    int MOD,m,n,T;
    scanf("%d%d",&T,&MOD);
    ans1[0] = 1;
    for(int i=1; i<N; i++)
        ans1[i] = ans1[i-1] * i % MOD;
    inv[1] = 1;
    for(int i=2;i<N;i++)
    {
        if(i >= MOD) break;
        inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
    }
    ans2[1] = 1;
    for(int i=2; i<N; i++)
    {
        if(prime[i])
        {
            ans2[i] = ans2[i-1] * (i - 1) % MOD;
            ans2[i] = ans2[i] * inv[i % MOD] % MOD;
        }
        else
        {
            ans2[i] = ans2[i-1];
        }
    }
    while(T--)
    {
        scanf("%d%d",&n,&m);
        LL ans = ans1[n] * ans2[m] % MOD;
        printf("%lld
",ans);
    }
    return 0;
}

 

接下来还有一个关于逆元的有意思的题目，描述如下

     

证明：由

     

     其中

     所以只需要证明，而我们知道模的逆元对应全部

     中的所有数，既是单射也是满射。

     所以进一步得到

      

      证明完毕！