【数学】同余基本概念与快速幂

同余基本概念与快速幂

基本概念与性质

• 定义：$a\equiv b(\mod m)$
• 定义的等价条件：$m\mid (a-b)\Leftrightarrow \exist k\in N,a=b+km$
• $\Rightarrow c\in N,a\pm c\equiv b\pm c(\mod m),ac\equiv bc(\mod m)$
• $\Rightarrow a^n\equiv b^n,n>0$
• $\Rightarrow f(a)\equiv f(b),f(x)整系数多项式$
• $\Rightarrow\gcd(a,m)=\gcd(b,m)$
• $,d\mid m\Rightarrow a\equiv b(\mod d)$
• 同余是等价关系（自反、对称、传递）
• 模$m$ 剩余类：将整数分成$m$ 个集合使得任意两个整数模$m$ 同余
• 模$m$ 完全剩余系：从模$m$ 的每个剩余类中选一个数，构成的$m$ 个数的集合
• $a\equiv b(\mod m),c\equiv d(\mod m)\Rightarrow ax+cy\equiv bx+dy(\mod m),x,y\in N,ac\equiv bd(\mod m)$
• $ac\equiv bc(\mod m),\gcd(c,m)=d\Rightarrow a\equiv b(\mod m/d)$
• $ab\equiv(a\%m)(b\%m)(\mod m)$

乘法改加法

防止乘法溢出的方法，原理跟计组里的乘法器很像：

// 计算a*b mod m，防止溢出
// 其中里面的取模为了更快还可以改成if(ans > m) ans -= m;
ll multi_add(ll a, ll b, ll m)
{
    a %= m;
    b %= m;
    ll ans = 0;
    while (b > 0)
    {
        if (b & 1)
        {
            ans += a;
            if(ans > m)
                ans -= m;
        }
        b >>= 1;
        a <<= 1;
        if(a > m)
            a -= m;
    }
    return ans;
}

逆元

定义：$\gcd(a,m)=1,ax\equiv 1(\mod m)$ ，$x$ 的解即为$a$ 的逆。

分数逆元：$\frac{a}{b}\mod m=a\cdot b^{-1} \mod m$

方法一：费马小定理

定理：$\gcd(a,m)=1,m为素数\Rightarrow a^{m-1}\equiv 1(\mod m)\Leftrightarrow a\cdot a^{m-2}\equiv 1(\mod m)$

用快速幂求$a^{p-2}$ 即可。

inline ll inv(int a) { return qpow(a, m - 2, m); }

方法二：拓展欧几里得

$a\cdot inv(a)\equiv 1(\mod m)$ ，拓展欧几里得解出$ax+my=1$ 答案，注意防止负数即可。

inline ll inv(ll a)
{
    ll x, y, d;
    exgcd(a, m, d, x, y);
    return d == 1 ? (x % m + m) % m : -1; // 不互质无解
}

方法三：线性递推

将$m$ 表示为$m=kx+y$ ，其中$k=\lfloor m/x\rfloor,y=m\%x$ 。则$kx+y\equiv 0(\mod m)$ ，同乘$inv(x)inv(y)$ ，则有$k\cdot inv(y)+inv(x)\equiv 0(\mod m)$ ，得$inv(x)\equiv -k\cdot inv(y)(\mod m)$

令$inv(x)=-k\cdot inv(y)=-\lfloor m/x\rfloor\cdot inv(m\%x)\mod m$ ，即一个数的逆元可由一个比它小的数的推出来。把负数消掉即可。

注：$m$ 可以不是素数

// inv[1...last]是1...last的逆元
inline void init(ll inv[], ll last, ll m)
{
    inv[1] = 1;
    for (ll i = 2ll; i <= last;i++)
        inv[i] = (m - m / i) * inv[m % i] % m;
}

阶乘逆元

// fac[i]=i!, inv[i]=inv(i!)
int fac[N],inv[N];
void init(int n)
{
    fac[0]=1;
    for(int i=1;i<=n;i++)
        fac[i]=1ll*fac[i-1]*i%mod;
    inv[n]=qpow(fac[n],mod-2); // 快速幂
    for(int i=n-1;i>=0;i--)
        inv[i]=1ll*inv[i+1]*(i+1)%mod;
}

快速幂

普通快速幂

形式：$x^n \mod m$

原理：将$n$ 拆成二进制，原式变为$x^{n_0\times 2^{0}+n_1\times 2^{1}+\cdots+n_k\times 2^{k}}=x^{n_0\times 2^{0}}\cdot x^{n_1\times 2^{1}}\cdots x^{n_k\times 2^{k}}=(x^{2^{0}})^{n_0}\cdot(x^{2^{1}})^{n_1}\cdots(x^{2^{k}})^{n_k}$ ，每次计算都取模，结果不变。

// 快速幂：计算x^n mod m
ll qpow(ll x, ll n, ll m)
{
    ll ans = 1ll;
    while (n)
    {
        if (n & 1)
            ans = ans * x % m;
        x = x * x % m;
        n >>= 1;
    }
    return ans;
}

矩阵快速幂

形式：$n\times n$ 的矩阵$A$ 的$k$ 次方：$A^k$

与普通快速幂原理一样。

struct matrix
{
    ll a[N][N];
    ll m;
    int n;
    matrix(int x = 0, ll mod) : n(x), m(mod) {}
    void build() // 读入矩阵
    {
        scanf("%d", &n);
        scanf("%lld", &m);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                scanf("%lld", &a[i][j]);
    }
    void init() // 矩阵初始化为单位矩阵
    {
        for (int i = 1; i <= n; i++)
            a[i][i] = 1ll;
    }
    matrix operator*(const matrix &b)
    {
        matrix nxt;
        for (int k = 1; k <= n; k++)
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++)
                    nxt.a[i][j] = (nxt.a[i][j] + a[i][k] % m * b.a[k][j] % m) % m;
        return nxt;
    }
};
matrix matrix_qpow(matrix A, ll k)
{
    matrix ans(A.n, A.m);
    ans.init();
    while (k)
    {
        if (k & 1)
            ans = ans * A;
        A = A * A;
        k >>= 1ll;
    }
}