[number theory] congruence (7): fast power, fast power of matrix

The congruence problem is 7part, My blog links ：

• Basic concepts and properties
• Inverse element ： Concept 、 Solution method and derivation
• Linear congruence equation
  • Univariate linear congruence equation
  • Univariate Linear Congruence Equations
  • Multivariate linear congruence equation
• Higher order congruence equation ：BSGS Algorithm （ Large and small step algorithm 、 Bashan algorithm ）
• Fast power and fast power of matrix

Fast power

Ordinary fast power

form ：$x^n\mathrm{m}\mathrm{o}\mathrm{d}m$

principle ： take $n$ Split into binary , The original formula becomes $$\begin{array}{rl}& 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}\end{array}$$

//  Fast power ： Calculation 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 >>= 1ll;
    }
    return ans;
}

Matrix fast power

form ：$n\times n$ Matrix $A$ Of $k$ Power ：$A^k$

Like the ordinary fast power principle , It's just matrix multiplication

struct matrix
{
    
    ll a[N][N];
    ll m;
    int n;
    matrix(int x = 0, ll mod) : n(x), m(mod) {
    }
    void build() //  Read in the matrix 
    {
    
        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() //  The matrix is initialized to the identity matrix 
    {
    
        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] % m + 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;
    }
}