乘法逆元&lucas定理

乘法逆元&lucas定理

乘法逆元

乘法逆元性质

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

乘法逆元证明

设$inv(x)$为b的逆元且n为质数

即$a/b ≡ a*inv(b)(mod n)$

a ≡ a * b * inv(b) (mod n)$

b*inv(b) ≡ 1 (mod n)$

由费马小定理可得$b ^ {n - 1} ≡ 1 (mod n)$

所以$b * b ^ {n - 2} ≡ 1 (mod n)$

故n为质数时，$inv(b) = b^{n - 2}$

很显然如果$a$是$n$的倍数则逆元不存在

代码

#include <iostream>
using namespace std;
#define ll long long
ll t;
ll qim(ll a, ll b, ll m){
    ll res = 1;
    while(b){
        if(b & 1){
            res *= a;
            res %= m;
        }
        a *= a;
        a %= m;
        b >>= 1;
    }
    return res;
}
int main(){
    cin >> t;
    while(t --){
        ll a, b; cin >> a >> b;
        ll res = qim(a, b - 2, b);
        if(a % b) cout << res << endl;
        else cout << "impossible" << endl;
    }
    return 0;
}

lucas定理

lucas定理的作用

lucas定理是一个与组合数有关的数论定理，根据组合定义$C^n_m = m! / {n!(m - n)!} = {m * (m - 1) * ··· * (m - n + 1)} / n!$如果当$m > 30$很明显数值无法用$longlong$承担,不过我们可以通过乘法逆元将除法转换为乘法$C^n_m ≡ m! * inv(n!) * inv[(m - n)!] (mod P)$,虽然可以通过这种方式解决问题，但有时候质数$P<m!$,这样就无法保证$n!$与$m-n!$的逆元是否存在了,因为有可能是$P$的倍数,这时候就要使用lucas定理

lucas定理

对于非负整数 $n,m$和质数 $P$，$C^n_m ≡ \prod_{i = 0}^k{C^{n_i}_{m_i}} (mod P)$ ，其中$m = m_kp^k + ··· +m_1p + m_0, n = n_kp^k+···+n_1p+n_0$ 是$m$ 和$n$ 的$p$进制展开,式子也可得$C^n_m=C^{n\%p}_{m\%p}⋅C^{⌊n/p⌋}_{⌊m/p⌋}(modp)$

lucas定理证明

前置知识:

二项式公式$(a+b)^n=C^0_nb^n+C^1_na^1⋅b^{n−1}+⋯+C_n^na^n=\sum_{k = 0}^n{C^k_na^kb^{n-k}}$

式子一:$C^x_p≡0(modp), 0<x<p$ 其中$p$为质数

由于 $0<x<p$，并且 $p$ 是质数，所以$C^x_p=p!/{x!*(p−x)!}=p*(p−1)!/{x*(x−1)!*(p−x)!}=p/x*C^{x−1}_{p−1}$

因为 $x < p$,所以$p/x$存在$x$膜$p$意义下的逆元$inv(x)$

$C^x_p≡p*inv(x)*C^{x-1}_{p-1} (mod p)$

显然右边为膜数$p$的倍数，所以$C^x_p≡0 (mod p)$

式子二:$(1+x)^p≡1+x^p(modp)$

由二项式展开可得:$(1+x)^p=C^0_px^p+C^1_p⋅x^{p−1}+⋯+C_p^p=\sum_{k = 0}^p{C^k_px^{k}}$

将式子一代入可得:$(1+x)^p ≡ 1 + x^p (mod p)$

lucas定理证明: $C^n_m=C^{n\%p}_{m\%p}⋅C^{⌊n/p⌋}_{⌊m/p⌋}(modp)$

设$\{^{⌊n/p⌋ = q_n}_{⌊m/p⌋ = q_m},\{_{m\%p = r_m}^{n\%p = r_n},\{_{m=q_mp+r_m}^{n=q_np+r_n}$

再由二项式定理$(1+x)^m=\sum_{k = 0}^m{C^k_mx^{k}}$

可得$(1+x)^m=(1+x)^{q_mp+r_m}=(1+x)^{q_mp}*(1+x)^{r_m} = [(1+x)^p]^{q_m}*(1+x)^{r_m}≡(1+x^p)^{q_m}*(1+x)^{r_m}=\sum_{i = 0}^{q_m}{C^i_{q_m}x^{pi}}*\sum_{j = 0}^{r_m}{C^j_{r_m}x^{j}}=\sum^{q_m}_{i = 0}\sum^{r_m}_{j=0}{C^i_{q_m}C^j_{r_m}x^{pi+j}} (mod p)$

之后归纳总结出$x^{ip+j}$的系数$k = ip+j$

得:$(1+x)^m≡\sum^{m}_{i = 0}{C^{⌊i/p⌋}_{q_m}C^{⌊n\%p⌋}_{r_m}x^{i}} (mod p)$

$\sum^{m}_{k = 0}{C^{k}_{m} x^k} ≡ \sum^{m}_{i = 0}{C^{⌊i/p⌋}_{q_m}C^{⌊n\%p⌋}_{r_m}x^i} (mod p)$

$\sum^{m}_{k = 0}{C^{k}_{m}} ≡ \sum^{m}_{i = 0}{C^{⌊i/p⌋}_{q_m}C^{⌊n\%p⌋}_{r_m}} (mod p)$

对比系数，且$k=n$，则$C^n_m≡ C^{n\%p}_{r_m}⋅C^{⌊n/p⌋}_{q_m}≡ C^n_m=C^{n\%p}_{m\%p}⋅C^{⌊n/p⌋}_{⌊m/p⌋} (modp)$ 得证

代码

#include <iostream>
using namespace std;
#define ll long long
ll t;
ll a, b, p;
ll qim(ll a, ll b, ll p){
    ll res = 1;
    while(b){
        if(b & 1){
            res *= a;
            res %= p;
        }
        a *= a;
        a %= p;
        b >>= 1;
    }
    return res;
}
ll C(ll a, ll b){
    ll res = 1;
    for(ll i = 1, j = a; i <= b; j --, i ++){
        res = (j * res) % p;
        res = (res * qim(i, p - 2,  p)) % p;
    }
    return res;
}
ll lucas(ll a, ll b, ll p){
    if(a < p && b < p ) return C(a, b);
    return C(a % p, b % p) * lucas(a / p, b / p, p) % p;
}
int main(){
    cin >> t;
    while(t --){
        cin >> a >> b >> p;
        cout << lucas(a, b, p) << endl;
    }
    return 0;
}