二进制划分

二进制划分是指，每个整数都有其二进制表示，每个整数都可以表示为若干个2的次幂相加。只要将整数的二进制数写出来，就可以得出该整数由哪些2的次幂组成，完成整数的二进制划分。（划分时，每个2的次幂只用一次）

快速幂

计算a的k次方对p取模的值。

朴素方法是用乘法代替幂，需要进行k-1次运算，快速幂对k进行二进制划分，可以将运算量降低。

int quick_pow(int a, int k, int p) {
    int res = 1;
    while (k > 0) {
        if (k & 1) res = (res * a) % p;
        a = (a * a) % p;
        k >>= 1;
    }
    return res;
}

这里res * a和a * a非常容易溢出，所以一般需要转换为long long类型。

int quick_pow(int a, int k, int p) {
    int res = 1;
    while (k > 0) {
        if (k & 1) res = ((long long)res * a) % p;
        a = ((long long)a * a) % p;
        k >>= 1;
    }
    return res;
}

慢速乘

计算a乘以b对p取模的值。

通常是直接将a与b相乘，再对p取模，但是a与b相乘的结果非常容易溢出。（假定不使用long long）采用慢速乘，对b进行二进制划分，虽然运算量变大，但可以避免溢出。

int slow_mul(int a, int b, int p) {
    int res = 0;
    while (b > 0) {
        if (b & 1) res = (res + a) % p;
        a = (a + a) % p;
        b >>= 1;
    }
    return res;
}

int类型的溢出尚且可以通过转存为long long处理，但是long long类型的溢出别无他法，只能使用慢速乘。

long long slow_mul(long long a, long long b, long long p) {
    long long res = 0;
    while (b > 0) {
        if (b & 1) res = (res + a) % p;
        a = (a + a) % p;
        b >>= 1;
    }
    return res;
}

---