逆元的求法

#什么是逆元

设c是b的逆元，则有b*c≡1(mod m)；逆元可以理解为在取模情况下的一个数字的倒数。

#逆元的作用是什么

当求解公式：(a/b)%m 时，因b可能会过大，会出现爆精度的情况，所以需变除法为乘法。因为根据模数的性质，乘法是不会出现爆精度的现象的。

根据公式(a/b)%m = (a/b)1%m = (a/b)bc%m = ac(mod m);

可得a/b的模等于a*b的逆元的模；

总结来说逆元就是用于大数相除。

#怎么求逆元

1.扩展欧几里得

讲解请参见

typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y)		//加上&用于保存
{
	if(!b)
	{
		 x =1;
		y = 0;
	}
	ll ans = exgcd(a,b,y,x);
	y -= (a / b) * x;
	return ans;
}
//扩展欧几里得求逆元
ll inv1(ll a)
{
    ll x,y;
    exgcd(a,mod,x,y);
    return x = (x % mod + mod) % mod;		//防止出现负数的情况
}

           

2.费马小定理

讲解请看

//费马小定理求逆元

//快速幂
ll quick_pow(ll x,ll n)
{
    ll rec = 1;
    x %= mod;
    while(n)
    {
        if(n&1)rec = rec * x % mod;
        n = n>>1;
        x = (x * x) % mod;
    }
    return rec;
}

ll inv(ll a)
{
    return quick_pow(a,mod - 2);
}

           

3.线性筛选

推到公式

//逆元的线性筛选
int init(int n)
{
    inv[1] = 1;
    for(int i = 2;i <= n;i++)
    {
        inv[i] = inv[mod % i] * (mod - mod / i) % mod;
    }
    for(int i = 1;i <= n;i++)
        printf("%d ",inv[i]);
}
           

4.阶乘逆元的线性筛选

因为逆元的阶乘乘以逆元，在对mod取余等于1。因此n的阶乘逆元乘以n再取余可以得到n -1的逆元

int quick_pow(int a,int b)
{
    if(b < 0)
        return 0;
    int res = 1;
    while(!b)
    {
        if(b & 1)res = res * ans % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return res;
}

//逆元的线性筛选
int init(int n)
{
    inv[1] = 1;
    for(int i = 2;i <= n;i++)
    {
        inv[i] = inv[mod % i] * (mod - mod / i) % mod;
    }
    for(int i = 1;i <= n;i++)
        printf("%d ",inv[i]);
}

//阶乘逆元
int inti_fact(int x)
{
    fact[0] = 1;
    for(int i = 1;i <= x;i++)                   //计算阶乘
        fact[i] = fact[i - 1] * i % mod;
    inv_fact[x] = inti_fact(fact[x],mod - 2);
    for(int i = n;i >= 1;i--)
        inv_fact[i - 1] = inv_fact[i] * i % mod;//逆元乘以自己然后对mod取余得1
}