前言

从今天开始好好学数学orz

---

目录

• 快速幂运算
• 取模运算
  • 大整数取模
  • 大整数乘法取模
  • 幂取模

---

快速幂运算

如果我们要计算$a^n$的值，正常情况下需要将$a$乘以自身$n$次，而这种暴力的计算方法需要花费$O(n)$的时间。利用二分思想，快速幂运算算法能够将这种幂运算的时间复杂度降低至$O(\log n)$，从而大大提高计算速率。

对于$a^n$，如果我们采用$\underbrace{a\times a\times\cdots\times a}_{n个a}$的方式进行计算的话，我们需要进行$n$次乘法运算。如果我们采用分治的思想，每次将幂指数除以2（为了发现规律，我们先假设$n$为2的幂次方，这样每次都能刚好整除）：

• $a^n=a^\frac{n}{2}\cdot a^\frac{n}{2}$
• $a^n=a^\frac{n}{4}\cdot a^\frac{n}{4}\cdot a^\frac{n}{2}$
• $a^n=\underbrace{a\cdot a\cdot a^2\cdot a^4\cdots a^\frac{n}{4}\cdot a^\frac{n}{2}}_{\log_2 n + 1项}$

可见，如果我们能在$O(1)$的时间内计算出每一项的值，那么我们只需要进行$log_2 n +1$次乘法运算，就能够得到最终的结果。而对于每一项而言，它的值都可以通过由前一项进行平方计算得到，因此，在$O(1)$的时间内计算出每一项的值是可行的。

于是我们得到了一个时间复杂度为$O(\log n)$的计算$a^n$的值的算法。（$n$为2的幂次方）

那么对于一般的$a^n$呢？我们再观察一下刚刚得到的式子：

• $a^n=\underbrace{a\cdot a\cdot a^2\cdot a^4\cdots a^\frac{n}{4}\cdot a^\frac{n}{2}}_{\log_2 n + 1项}=a^{2^0+2^0+2^1+2^2+\cdots+2^{\log_2 n -1}}$

$a$的指数部分$2^0+2^0+2^1+2^2+\cdots+2^{\log_2 n -1}$很自然地让我们联想到十进制数的二进制表达，它们有着相似的形式。我们知道，任意的正整数$n$都能被表示成为若干个2的幂的和（十进制数能够被转化为二进制数），因此，对于一般的$a^n$，我们只需要将$n$表示为若干个2的幂的和，就可以将$a^n$表示为上述式子，从而以$O(\log n)$的时间复杂度计算$a^n$

即：令$n=\underbrace{m_02^0+m_12^1+m_22^2+\cdots+m_{\lfloor\log_2 n\rfloor}2^{\lfloor\log_2 n\rfloor}}_{\lfloor\log_2 n\rfloor+1项}，m_i\in\{0,1\}$，则$a^n=a^{m_02^0}\cdot a^{m_12^1}\cdots a^{m_{\lfloor\log_2 n\rfloor}2^{\lfloor\log_2 n\rfloor}}$，其中$a_{i+1}=a_i^2$。

这就得到了快速幂运算算法。

下面给出一种非递归的C语言实现：

long long fpow(long long a, long long n)
{
    long long ans = 1;
    while (n)
    {
        if (n & 1)
            ans *= a;
        a *= a;
        n >>= 1;
    }
    return ans;
}

从$a$开始，如果$n$的二进制数末位不为零（即对应上式$m_i$不为零），则将该数乘入结果变量中，然后将$a$进行平方，移动到$m_{i+1}$，重复进行判断。可见，我们需要进行$\lfloor\log_2 n\rfloor+1$次乘法运算与平方运算，故时间复杂度为$O(\log n)$

---

取模运算

大整数取模

一般情况下，如果某个题目的答案是一个超过long long存储范围的大整数，大部分题目并不会要求直接输出该大整数作为答案，而是要求输出这个大整数对某个数取模的结果。

输入正整数$n$和$m$，输出$n\bmod m$的值。$n\leq10^{100}，m\leq10^9。$

在开始之前，我们需要知道一些模运算的基本性质：

• $(a+b)\bmod n=((a\bmod n)+(b\bmod n))\bmod n$
• $(a-b)\bmod n=((a\bmod n)-(b\bmod n))\bmod n$
• $ab\bmod n=(a\bmod n)(b\bmod n)\bmod n$

可以看到，两个数相加/相减/相乘之后再对某一个数取模，等于各个数对这个数分别取模再相加/相减/相乘的结果对这个数取模。值得注意的是，如果各个数对这个数分别取模再相加/相减/相乘的结果小于这个数的话，则最后的取余是不必要的。
即：

• 若$a\bmod m+b\bmod m<m$，则有：$(a+b)\bmod n=a\bmod n+b\bmod n$
• 若$a\bmod m-b\bmod m<m$，则有：$(a-b)\bmod n=a\mod n-b\mod n$
• 若$(a\bmod m)(b\bmod m)<m$，则有：$ab\bmod n=(a\bmod n)(b\bmod n)$

那么，对于一个两位数$x=10a+b$，由上面的基本性质我们可以进行以下推导：

1. $x\bmod m=(10a+b)\bmod m$
2. 令$a=km+r，则x\bmod m=(10km+10r+b)\bmod m$
3. $(10km+10r+b)\bmod m=(10km\bmod m)+(10r+b)\bmod m=(10r+b)\bmod m$
4. $\because r=a\bmod m，\therefore x\bmod m=(10\times (a\bmod m)+b)\bmod m$

有了这样一个式子，我们就可以对大整数$n$（假定为1234）进行取模了：

1. 将大整数$n$分解为“自左向右”的形式：$1234=((1\times 10+2)\times 10+3)\times 10+4$
2. 对于每一个$10a+b$型的括号，采用$(10\times (a\bmod m)+b)\bmod m$的方式进行取模

int bmod(char *num, int len, int m)
{
    int ans = 0;
    for (int i = 0; i < len; i++)
        ans = (int)((1ll * ans * 10 + num[i] - '0') % m);
    return ans;
}

算法的时间复杂度随正整数的位数线性增长。

大整数乘法取模

计算$a\times b\bmod m，a,b\le m\le 10^{18}$。

对于这一类型的取模，我们当然可以使用高精度计算得到$a\times b$的结果，再通过大整数取模方法进行计算。不过，我们还有更为高效的做法。

由模运算的基本性质，我们知道，取模运算可以通过将大数拆分为一个个小的模块分别取模再处理来简化运算。然而，如果对$a,b$分别取模再相乘，其结果仍然可能溢出。因此，我们不妨先从拆分$a\times b$入手。

我们可以借鉴快速幂运算中的思想，将其中一个乘数表示为若干个2的整数次幂的和的形式：

• 令$a=m_02^0+m_12^1+m_22^2+\cdots+m_{\lfloor\log_2 n\rfloor}2^{\lfloor\log_2 n\rfloor}，m_i\in\{0,1\}$
• $a\times b=m_02^0\times b+m_12^1\times b+m_22^2\times b+\cdots+m_{\lfloor\log_2 n\rfloor}2^{\lfloor\log_2 n\rfloor}\times b$

这样，两个大整数的相乘计算就转化为了相加计算，我们可以在相加的过程中进行取模运算，从而能够防止在计算过程数据溢出。

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

与快速幂运算类似，第$i$项表达式的值可以由第$i-1$项表达式乘以2得到。因此，我们需要进行$\lfloor\log_2 n\rfloor+1$次加法操作。故该算法的时间复杂度为$O(\log n)$

幂取模

我们常常会遇到这样的问题：

计算$x^n\bmod m$。

由模运算的基本性质容易知道，我们只需要在相乘的过程进行取模运算即可。使用快速幂运算算法计算$x^n$，很容易在$O(\log n)$的时间内得到这一问题的解：

long long fpow_mod(long long x, long long n, long long m)
{
    x %= m; // 预处理x，避免第一次进行平方运算时溢出
    long long ans = 1;
    while (n)
    {
        if (n & 1)
            ans = ans * x % m;
        x = x * x % m;
        n >>= 1;
    }
    return ans;
}

对于$m$为质数的幂取模计算，我们还可以利用费马小定理来提高算法效率。

费马小定理(Fermat’s little theorem)是数论中的一个重要定理，在1636年提出。如果p是一个质数，而整数a不是p的倍数，则有$a^{p-1}≡1（\bmod p）$。

若$x$与$m$互质，$m$为质数，则有：

• $x^n=x^{k(m-1)+n\bmod (m-1)}\bmod m=x^{k(m-1)}\bmod m+x^{n\bmod(m-1)}\bmod m=x^{n\bmod(m-1)}\bmod m$

在大多数题目中，$m$往往等于1000000007。这是一个很特别的数：

1. $1000000007$是一个质数。
2. $1000000007\times 2$仍在int的数据范围内，换句话说，对于int型变量$a,b$，利用模运算的基本性质计算$(a+b)\bmod 1000000007$的过程中不会溢出。
3. $1000000007^2$仍在long long的数据范围内，换句话说，对于long long型变量$a,b$，利用模运算的基本性质计算$a\times b\bmod 1000000007$的过程中不会溢出。

这简直是为费马小定理优化而生的数字呢。