基础数学知识

欧几里得算法：

欧几里得算法是求最大公约数的算法：是辗转相除法的具体实现

int gcd(int x, int y) {
    if (y == 0) return x;
    else {
        gcd(y, x % y);
    }
}

无需比较x, y的大小

扩展欧几里得算法：

扩展欧几里得算法是用于求逆元的。如果d与m互质—>(cd) % m == 1，那么c是d关于模m的逆元。
由题意：c _ d == k m + 1;形如a x + b _y = 数。
变形：c d + k * m == 1;
已知：d,m—>求c的可能取值

void exgcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1; y = 0;
    }
    else {
        exgcd(b, a % b, y, x);
        y -= a / b * x;
    }
}
exgcd(d, m, x, y);
c = (x%m + m)%m;

同余理论：

(a + b) % m == (a % m + b %m) % m;
(a _ b) % m == (a % m b %m)%m;_

快速乘理论：

因为 a * b 可能会爆long long—>所以将乘法转换为加法进行计算。

int mul(int a, int b) {
    int ans = 0;
    while (b) {
        if (b & 1) {
            ans = (ans + a);
        }
        a += a;
        b >>= 1;
    }
    return ans;
}

因为快速乘算法一般还涉及余数的处理问题，所以（a * b) % m的快速乘版本：

int Qmul(int a, int b, int m) {
    int ans = 0;
    while (b) {
        if (b & 1) {
            ans = (ans % m + a % m) % m;
        }
        a = (a % m + a % m) % m;
        b >>= 1;
    }
    return ans;
}

快速幂原理：

因为a^b极易超时或者范围爆炸，所以快速乘

int Qpower(int a, int b) {
    int ans = 1;
    while (b) {
        if (b & 1) {
            ans *= a;
        }
        a *= a;
        b >>= 1;
    }
    return ans;
}

取余情况下的快速幂算法：—>余数为m

int Qpower(int a, int b, int m) {
    int ans = 1;
    while (b) {
        if (b & 1) {
            ans = ((ans % m) * a % m) % m;
        }
        a = (a % m * a % m) % m;
        b >>= 1;
    }
    return ans;
}