题解：P5091 【模板】扩展欧拉定理

· · 题解

更新于 2025/9/9：增加了欧拉函数 \Theta(\sqrt n) 复杂度求法的证明。

一、欧拉函数

表示：\varphi(n)。\ 意义：在 [1,n] 区间内，与 n 互质的整数的个数。

如何计算欧拉函数？

方法一：暴力法

暴力计算 \sum_{i=1}^{n}[\gcd(i,n)=1]。其中的方括号为艾弗森括号，括号内的式子成立，值为 1，否则为 0。代码省略。

时间复杂度 \Theta(n \log n)，原因：一次求 \gcd 是 \Theta(\log n) 的，而需要 n 次枚举。

方法二：质因数分解法

我们假设 n 能分解为如下形式：

n = p_1^{t_1} \times p_2^{t_2} \times \cdots p_k^{t_k}

其中 \forall p_i \in \text{prime} 且 \forall t_i \in \N^{*}。

那么：

\varphi(n) = n\prod_{i=1}^{k} \dfrac{p_i - 1}{p_i}

代码：

int phi(int x){
    int ans = x; //初始化
    for(int i = 2; i * i <= x; ++i){
        if(x % i == 0){ //存在该质因数
            while(x % i == 0) x /= i; //将所有质因数给除完
            ans /= i;
            ans *= (i - 1); //等价于乘上 (i - 1) / i，也就是计算上式的其中一项
        } 
    } 
    if(x > 1)
        ans /= x, ans *= (x - 1); //出现剩余特判
    return ans; 
}

时间复杂度 \Theta(\sqrt{n})，等同于朴素分解质因数的复杂度，证明略。\

::::success[正确性证明]{open}

引理：\varphi(p^t) = p^{t-1}\times (p-1)。
由欧拉函数的定义，及因式分解易证。

我们令 n = \prod_{i=1}^{t} p_{i}^{t_i}，其中 \forall p_i \in \text{prime}, \forall t_i\in \N^{*}。

根据欧拉函数的积性，可以得到 \varphi(n) = \prod_{i=1}^{k} \varphi(p_{i}^{t_i})。
根据引理，变形上式得 \varphi(n) = \prod_{i=1}^{k} p_i^{t_i-1} \times (p_i - 1)。
由于 ab = ap^{-1} \times bp，所以依此变形上式得 \varphi(n) = \prod_{i = 1}^{k} p_i^{t_i} \times \dfrac{p_i-1}{p_i}。
由乘法结合律得 \varphi(n) = (\prod_{i=1}^{k} p_i^{t_i})(\prod_{i=1}^{k}\dfrac{p_i-1}{p_i})。
将原假设代入得 \varphi(n) = n \prod_{i=1}^{k} \dfrac{p_i-1}{p_i}。

原命题得证。 ::::

二、欧拉定理

内容

若 \gcd(a,m) = 1，则 a^{\varphi(m)} \equiv 1 \pmod m。

证明

原命题得证。

三、扩展欧拉定理

内容

设 a,b,m 为正整数，则：

a^b \equiv \begin{cases} a^b \pmod m & b < \varphi(m) \\ a^{b \bmod \varphi(m) + \varphi(m)} \pmod m & b \ge \varphi(m) \end{cases}

证明

分多种情况讨论。

情况一：b < \varphi(m)

如果不会证这个建议重修幼儿园数学（不是）。

情况二：b > \varphi(m),\gcd(a,m) = 1

套普通欧拉定理就行，你们自己证吧我跑了。

接下来的两种情况，我们需要对 a 分解质因数，假设其为如下形式：

a = p_1^{t_1} \times p_2^{t_2} \times \cdots p_k^{t_k}

现在问题等价于：a 的每个质因子 p_i 满足原条件就行。\ 为啥？因为保证 a\equiv b \pmod x 且 a\equiv b \pmod y 必须要满足 a\equiv b \pmod {\operatorname{lcm}(x,y)}，能用 CRT 证。根据这个定理对质因子进行合并就行。

显然这个时候要么 m\ |\ p_i，要么 \gcd(m,p_i) = 1。

情况三：\gcd(m,p_i) = 1

仍然是套普通欧拉定理所以我再跑。

a^b \equiv a^{\lfloor\frac{b}{\varphi(m)}\rfloor \varphi(m) + b \bmod \varphi(m)} \equiv a^{b \bmod \varphi(m)} \pmod {p_i^{t_i}}

情况四：m\ |\ p_i

不水了不水了，讲正经的。

首先需要插播一条欧拉函数的性质：若 x = p^k，则 \varphi(x) = p^k - p^{k-1}。\ 所以这个时候 \varphi(p_i^{t_i}) = p_i^{t_i} - p_i^{t_i - 1} = p_i^{t_i - 1}(p_i - 1)。

由于：

\varphi(m) \ge \varphi(p_i^{t_i}) = p_i^{t_i - 1}(p_i - 1) \ge t_i

故：

b\ge \varphi(m) \ge t_i

进一步得出：

a^b \equiv 0 \pmod {p_i^{t_i}}

因为 a,m 里面存在因子 p_i，而 b \ge t_i。同理，指数为 b \bmod \varphi(m) + \varphi(m) 时，因为 b\bmod \varphi(m) \ge 0，所以 b\bmod \varphi(m) + \varphi(m) \ge \varphi(m)\ge t_i。所以：

a^{b\bmod \varphi(m) + \varphi(m)} \equiv 0 \pmod {p_i^{t_i}}

两个同余式的左边一坨都和 0 同余，故：

a^b \equiv a^{b \bmod \varphi(m) + \varphi(m)} \pmod{p_i^{t_i}}

由于 a,b 对于 m 的每个质因子 p_i 都满足定理条件，将每个条件合并得：

a^b\equiv a^{b \bmod \varphi(m) + \varphi(m)} \pmod m

综上，原定理成立。

四、解题思路

套公式。

五、代码

#include<bits/stdc++.h>
#define int long long 
using namespace std;

int qpow(int a, int b, int m){ //快速幂
    int base = a, ans = 1;
    while(b > 0){
        if(b & 1) ans *= base, ans %= m;
        base = base * base % m, b >>= 1; 
    } 
    return ans; 
} 
int phi(int x){ //欧拉函数计算
    int ans = x;
    for(int i = 2; i * i <= x; ++i){
        if(x % i == 0){
            while(x % i == 0) x /= i;
            ans /= i;
            ans *= (i - 1); 
        } 
    } 
    if(x > 1)
        ans /= x, ans *= (x - 1); 
    return ans; 
} 
signed main(){
    int a, m, b = 0; cin >> a >> m;
    int ph = phi(m); char c = getchar();
    while(!isdigit(c)) c = getchar();

    bool flag = false;
    while(isdigit(c)){ //边读入边取模，高精度再见！
        b = (b << 3) + (b << 1) + (c ^ '0');
        if(b >= ph) flag = true, b %= ph; 
        c = getchar();
    } 
    if(flag) b += ph; //需要特判指数上是否加上 phi(m)
    cout << qpow(a, b, m); 
    return 0; 
}

六、时空复杂度分析