快速幂模板求逆元，逆元的作用以及例题【第20届上海大学程序设计联赛夏季赛】排列计数

乘法逆元的定义

若整数 b，m 互质，并且对于任意的整数 a，如果满足 b|a(整除)，则存在一个整数 x，使得 a/b≡a*x(mod m)，则称 x 为 b 的模 m 乘法逆元，记为 (mod m)。 b存在乘法逆元的充要条件是 b 与模数 m 互质。当模数 m为质数时， 即为 b 的乘法逆元。

所以可以用快速幂的模板求解逆元。

例题：876. 快速幂求逆元 - AcWing题库

题面：

 代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
const int mod=1e9+7;
//快速幂模板
int qmi(int a,int k,int p)
{
    int res=1;
    while(k)
    {
        if(k&1) res=(ll)res*a%p;
        k>>=1;
        a=(ll) a*a%p;
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    while(n--)
    {
        ll a,p;
        cin>>a>>p;
        if(a%p) cout<<qmi(a,p-2,p)<<endl;//只有当a不是p的倍数时，才有逆元。
//若a是p的倍数，则有a/b=0,不会同余于a*x了，即无逆元。
        else cout<<"impossible"<<endl;
    }
    return 0;
}

那我们来说说逆元的作用吧

先来说说加减乘除的求余概念

(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   （×）

这里不难看出来做除法取余是错的吧，看个例子：

(100/50)%20 = 2 ≠ (100%20) / (50%20) %20 = 0

对于一些题目，由于数字太大，电脑存不下，我们必须在中间过程中进行求余。若这个算式中出现除法，我们就不能先做除法再取模，由上面可知“除法取余是错的”，由此我们就需要用逆元来代替。

例题：E-排列计数_第20届上海大学程序设计联赛夏季赛（校外同步赛） (nowcoder.com)
 

题目描述

输入描述:

输出描述:

输出一行一个整数，表示满足条件的排列数，由于答案可能很大，请对1e9+7取模

示例1

输入

1

输出

1

示例2

输入

3

输出

360

由题目可以看出来，我们需要求的是2*n!/2的值输出。

如果直接写阶乘取模输出，当然会wa咯。

 这里稍微把那个除2的运算改成乘上2（模mod）的逆元再取模就会ac了。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
const int mod=1e9+7;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//快速幂模板
int qmi(int a,int k,int p)
{
    int res=1;
    while(k)
    {
        if(k&1) res=(ll)res*a%p;
        k>>=1;
        a=(ll) a*a%p;
    }
    return res;
}
int main()
{
    IOS;
    ll n;
    cin>>n;
    ll ans=1;
    for(int i=1;i<=2*n;i++)
        ans=(ans*i)%mod;
    cout<<ans*qmi(2,mod-2,mod)%mod<<endl;
    return 0;
}