逆元（inv）

推荐博客： http://blog.csdn.net/baidu_35643793/article/details/75268911

通常我们在计算除法取模时，并不能直接的取模后再去相除，答案会有问题，在这里我们就引入逆元的，(a/b)%mod = (a*c)%mod , 在这里 c 是 b 的逆元。

即 a/b 的模等于 a*b 的逆元的模；

求逆元的方法：

（1）费马小定理

　　在是素数的情况下，对任意整数都存在逆元。

　　题目中给定的对 P 去模，且 P 是素数，则数X的逆元就是 X^(p-2) 。

　代码示例：

const ll mod = 998244353;

ll qpow(ll x, ll cnt){

    ll ans = 1;

    while(cnt > 0){

        if (cnt&1) ans = (ans*x)%mod;

        x = (x*x)%mod;

        cnt >>= 1;

    }

    return ans;

}

注意 : 最后的答案一定要在取一次模才可以！

（2）扩展欧几里得

同余方程 ax = b (mod n) , 当 b = 1 时， ax = 1 (mod n) ，此时称 x 为 a 对模 n 得乘法逆元，那么就可以转换为 ax - ny = 1 ，逆元存在得条件时 gcd(a, n) = 1 。

代码示例：

void exgcd(ll a, ll b, ll &g, ll &x, ll &y){

    if (b == 0) {g = a; x = 1; y = 0;}

    else {

        exgcd(b, a%b, g, y, x);

        y -= (a/b)*x;

    }

}

ll inv(ll a, ll n){

    ll d, x, y;

    exgcd(a, n, d, x, y);

    return d == 1?(x+n)%n:-1;

}

(3) 欧拉函数

当 p 是素数的时候，由费马小定理值 a^(p) = a (mod p) , 那么则有 a ^ (p-1) = 1 (mod p) , 在变形则由 a ^ (p-2) = a^(-1) (mod p)

当 p 不是素数得时候，这时候就需要借助欧拉函数,

a^(phi(p)) = 1 (mod p)

a*a^(phi(p)-1)≡1 (mod p)

a^(-1)≡a^(phi(p)-1) (mod p)

巴特西

逆元（inv）

最新文章

热门文章