欧拉函数 & 快速幂 & 扩展欧几里得算法 & 中国剩余定理

欧拉函数

定义：$\phi (n)$ 表示 $1$ ~ $n$ 中与 $n$ 互质的数的个数（1与任何数互质）

求欧拉函数 —— 模板题 AcWing 873. 欧拉函数

• 公式：由 $$N=p_{1}^{\alpha _{1}}·p_{2}^{\alpha _{2}}·…·p_{k}^{\alpha _{k}}$$ 得 $$\phi (n)=N(1-\frac{1}{p_1})(1-\frac{1}{p_2})…(1-\frac{1}{p_k})$$
• 证明：容斥原理 $$\phi (n)=N-\frac{N}{p_1}-\frac{N}{p_2}-…-\frac{N}{p_k}+\frac{N}{p_1p_2}+\frac{N}{p_1p_3}+…=N(1-\frac{1}{p_1})(1-\frac{1}{p_2})…(1-\frac{1}{p_k})$$

时间复杂度：瓶颈在分解质因数，$O(\sqrt{n})$

模板

int phi(int x)
{
    int res = x;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            res = res / i * (i - 1);                //由于这里是整除，因此要先除以i再乘，而不能有 1/i
            while (x % i == 0) x /= i;
        }
    if (x > 1) res = res / x * (x - 1);

    return res;
}

• 代码

筛法求欧拉函数 —— 模板题 AcWing 874. 筛法求欧拉函数

• 要求 $1$ ~ $n$ 中每一个数的欧拉函数时，上述求法比较慢，可以采用线性的优化
• 借助线性筛法的算法来优化
• 关键：( pj 表示质数)
  • 当 i % pj == 0 时，phi[pj * i] = pj * phi[i] 。因为求 $\phi (i)$ 时已经乘过了 $1-\frac{1}{p_j}$
  • 当 i % pj != 0 时，phi[pj * i] = (pj - 1) * phi[i]。要多乘 $p_j(1-\frac{1}{p_j})=p_j-1$

时间复杂度：$O(n)$

模板

int primes[N], cnt;     // primes[]存储所有素数
int euler[N];           // 存储每个数的欧拉函数
bool st[N];         // st[x]存储x是否被筛掉


void get_eulers(int n)
{
    euler[1] = 1;
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
        {
            primes[cnt ++ ] = i;
            euler[i] = i - 1;
        }
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            int t = primes[j] * i;
            st[t] = true;
            if (i % primes[j] == 0)
            {
                euler[t] = euler[i] * primes[j];
                break;
            }
            euler[t] = euler[i] * (primes[j] - 1);
        }
    }
}

• 代码

欧拉定理（费马-欧拉定理或欧拉 $\phi$ 函数定理）

• 若 $a$ 与 $n$ 互质，则 $$a^{\phi (n)}\equiv 1\pmod n$$
• 一些概念
  • 剩余类：所有模 $n$ 相同的数构成 $n$ 的一个剩余类
    • 与 $n$ 互素的剩余类：剩余类中所有数都与 $n$ 互质
  • 完全剩余系：$n$ 的所有剩余类中各取一个数构成的集合，集合里每个数对 $n$ 的余数取遍 $0$ ~ $n - 1$ 而不重复
  • 简化剩余系：完全剩余系中所有与 $n$ 互质的数构成的集合，或 $n$ 的所有与 $n$ 互质的剩余类中各取一个数构成的集合
  • 证明：若 $a$ 与 $n$ 互质，$A=\{a_1,a_2,…,a_{n-1}\}$ 是 $n$ 的一个完全剩余系，则 $A’=\{aa_1,aa_2,…,aa_{n-1}\}$ 也是 $n$ 的一个完全剩余系
    • 假设 $A’$ 不是 $n$ 的完全剩余系，则存在 $$aa_i\equiv aa_j\pmod n$$ $$a(a_i-a_j)\equiv 0\pmod n$$
    • 因为 $n$ 与 $a$ 互质，所以 $$a_i-a_j\equiv 0\pmod n$$ $$a_i\equiv a_j\pmod n$$ 与 $A$ 是完全剩余系矛盾
    • 综上，结论成立
  • 证明：若 $a$ 与 $n$ 互质，$A=\{a_1,a_2,…,a_{\phi (n)}\}$ 是 $n$ 的一个简化剩余系，则 $A’=\{aa_1,aa_2,…,aa_{\phi (n)}\}$ 也是 $n$ 的一个简化剩余系
    • 证明 $A’$ 中不存在同余的数做法同上
    • 若存在 $aa_{i}\in A’ 且 a_{j}\notin A$ , $aa_{i}\equiv a_{j}\pmod n$ ,则 $a_{j}$ 不与 $n$ 互质，$aa_{i}$ 也不与 $n$ 互质
    • 因为 $a和a_{i}$ 都与 $n$ 互质，所以 $aa_{i}$ 一定与 $n$ 互质，矛盾
    • 综上，结论成立
• 费马小定理：若 $p$ 是一个质数，则 $$a^{p-1}\equiv 1\pmod p$$
  • 证明：构造上述的 $A和A’$,由上述证明可知下式成立 $$\prod_{i=1}^{p-1}i\equiv \prod_{i=1}^{p-1}ai$$ $$(a^{p-1}-1)\prod_{i=1}^{p-1}i\equiv 0\pmod p$$ $$a^{p-1}\equiv 1\pmod p$$
• 费马-欧拉定理是费马小定理的推广，证明就是把完全剩余系换成简化剩余系
• 一般的欧拉定理是指几何和图论中 $n(点数)-m(边数)+r(面数)=2$

快速幂

快速幂 —— 模板题 AcWing 875. 快速幂

• 求 $a^{k}\bmod p$ 传统循环指数 $k$ 次，时间复杂度是 $O(k)$ 的一个并不 $ok$ 的复杂度
• 优化
  • 例如，计算 $7^{10}$ ,如果是
    int res = 1; for(int i = 0;i < 10;i ++) res *= 7;
    那不仅时间慢，而且无法发挥CPU的计算能力
  • 可以这样计算：先算 $7^{5}$ ,再算它的平方
  • $7^{5}$ 也可以拆成 $(7^{2})^{2}\times 7$
  • 于是 $7^10$ 就被拆成了 $$(7^{2})^{2}\times 7\times (7^{2})^{2}\times 7=7^{2^{3}}\times 7^2$$
  • 可以发现，$2^3+2=10$ 就是 $10$ 的二进制表示换算回十进制的算式
  • 通过这样的分法，如果我们要求 $a^n$ ,就可以通过较少的循环求出 $$\{a^{2^{1}} a^{2^{2}}…a^{2^{\log k}}\}$$ 并按照 $n$ 的二进制转化十进制算式，通过这些结果的线性组合得到 $a^n$

时间复杂度： $O(\log k)$

模板

求 m^k mod p，时间复杂度 O(logk)。

int qmi(int m, int k, int p)
{
    int res = 1 % p, t = m;
    while (k)
    {
        if (k&1) res = res * t % p;
        t = t * t % p;
        k >>= 1;
    }
    return res;
}

• 代码

快速幂求逆元

• 计算机在进行大数运算时经常会碰到溢出或数据删除的情况，一般想到的是进行高精度优化。但如果某些情况下不需要知道计算结果的全貌，而只需要知道计算结果对一个数的取模结果时，就可以用取模运算去进行优化。如加法：$$(a+b)\bmod n=(a\bmod n)+(b\bmod n)$$ 减法：$$(a-b)\bmod n=((a\bmod n)+n-(b\bmod n))\bmod n$$ 乘法：$$a\times b\bmod n=((a\bmod n)\times(b\bmod n))\bmod n$$
• 但当除法需要优化时，却不存在 $$\frac{a}{b}\bmod n=\frac{a\bmod n}{b\bmod n}$$ ，无法进行优化
• 于是我们就用到了逆元的概念（模逆元）：若存在一个数 $x$ ，$$\frac{a}{b}\equiv a\times x\pmod n$$ 则称 $x$ 为 $b$ 的 $\bmod n$ 乘法逆元，记 $b^{-1}\pmod n$。通过求逆元。我们就可以把除法等价成乘法进行运算优化
• 逆元条件及性质：$$\frac{a}{b}\equiv a\times b^{-1}\pmod n$$ $$a\equiv a\times b^{-1}\times b\pmod n$$ 由于 $a$ 是任意一个数，因此 $$b^{-1}b\equiv 1\pmod n$$
  • 由上可以看出，$b$ 存在逆元的充要条件是 $b$ 与 $n$ 互质
  • $b$ 与 $b^{-1}$ 相当于 $\bmod n$ 下的倒数关系
• 注意 $$b^{-1}b\equiv 1\pmod n$$ 当 $n$ 为质数时有费马小定理 $$b^{n-1}\equiv 1\pmod n$$ 因此当 $n$ 为质数时 $b^{n-2}$ 为 $b$ 的 $\bmod n$ 下的乘法逆元。于是可以用快速幂算法求逆元
• 代码

扩展欧几里得算法

扩展欧几里得算法 —— 模板题 AcWing 877. 扩展欧几里得算法

• 裴蜀定理：对于任意正整数 $a b$ ，一定存在整数 $x y$ ,使得 $$ax+by=gcd(a,b)$$ 且 $gcd(a,b)$ 是 $a b$ 的线性组合结果中最小的正整数
  • 证明：若存在正整数 $d$， $$ax+by=d$$ 则 $d$ 一定是 $gcd(a,b)$ 的倍数。因此 $d_{min}=gcd(a,b)$
  • 详细证明及推广
• 拓展欧几里得算法就是求出 $x y$ 的算法
  • 解不唯一

模板

// 求x, y，使得ax + by = gcd(a, b)
int exgcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
        x = 1; y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= (a/b) * x;                 //还原b的系数（递归回来的算式中a的系数就是x，不用还原）
    return d;
}

• 代码

线性同余方程

• 给定 $n$ 组数据 $a_i,b_i,m_i$ ，对于每组数求出一个 $x_i$ ，使其满足 $a_i\times x_i\equiv b_i\pmod {m_i}$ ，如果无解则输出 impossible 。
  • $a_i\times x_i\equiv b_i\pmod {m_i}$ 成立等价于存在 $y$ ,使得 $ax=my+b$
  • 等价的式子可以用拓展欧几里得算法求解（注意变形）
• 通过扩展欧几里得算法求逆元：$$ax\equiv 1\pmod n$$
• 代码

中国剩余定理

验证图中 $x$ 的正确性：对于 $x\equiv a_{i}\pmod {m_{i}}$ ,项 $$a_{i}\times M_{i}\times M_{i}^{-1}\equiv a_{i}\times 1\pmod m_{i}$$ 其他项均是 $m_{i}$ 的倍数，因此 $x$ 满足要求

表达整数的奇怪方式

• 求中国剩余定理的最小解：找到一个满足要求的特解，再对除数的最小公倍数取模

具体算法：

- 代码

作者：yxc
链接：https://www.acwing.com/blog/content/406/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。