mobile wallpaper 1
mobile wallpaper 2
mobile wallpaper 3
mobile wallpaper 4
Profile Image of the Author
Stella
近期公告
博客搬迁中wordpress --> astro
标签
1501 字
5 分钟
欧拉函数与快速幂
2026-03-31
算法
欧拉函数
/
快速幂

欧拉函数与快速幂#

欧拉函数#

欧拉函数 φ(n) 是「小于等于 n 且与 n 互质的正整数个数」，记作

  φ(n) = |{ 1 ≤ k ≤ n : gcd(k, n) = 1 }|

它是一切「模运算、乘法群、RSA 密码」的基石

n = p₁^e₁ · p₂^e₂ … p_k^e_k

φ(n) = ∏ φ(pi^ei) 　　　　= ∏ pi^ei(1−1/pi) 　　　　= n · ∏(1−1/pi)

欧拉函数 φ(n) 是「小于等于 n 且与 n 互质的正整数个数」，记作
φ(n) = |{ 1 ≤ k ≤ n : gcd(k, n) = 1 }|

它同时是一个积性函数，也是 RSA、模逆、欧拉定理的基石。

一、定义与例子 n | 1 2 3 4 5 6 7 8 9 10 φ(n)|1 1 2 2 4 2 6 4 6 4 验证 φ(6)=2：{1,5} 与 6 互质。

二、通用公式 若 n = p₁^e₁ · p₂^e₂ … pk^ek （标准质因分解） 则 φ(n) = n · ∏{i=1..k} (1 − 1/pi) = ∏{i=1..k} (pi^ei − pi^{ei−1})

三、常用特例

  1. p 为素数 ⇒ φ(p) = p−1
  2. φ(p^e) = p^{e−1}(p−1)
  3. gcd(m,n)=1 ⇒ φ(mn)=φ(m)φ(n) （积性）

四、核心性质

  1. 约数和：∑_{d|n} φ(d) = n
  2. 欧拉定理：gcd(a,n)=1 ⇒ a^{φ(n)} ≡ 1 (mod n)
  3. 费马小定理：n 素数 ⇒ a^{n−1} ≡ 1 (mod n)

五、代码模板

  1. 单点 O(√n)
static long phi(long n) {
    long res = n;
    for (long p = 2; p * p <= n; p++)
        if (n % p == 0) {
            res = res / p * (p - 1);
            while (n % p == 0) n /= p;
        }
    if (n > 1) res = res / n * (n - 1);
    return res;
}
  1. 线性筛批量 φ[1..n] O(n)
static int[] phiTable(int n) {
    int[] phi = new int[n + 1];
    for (int i = 0; i <= n; i++) phi[i] = i;
    for (int i = 2; i <= n; i++)
        if (phi[i] == i)             // i 是质数
            for (int j = i; j <= n; j += i)
                phi[j] = phi[j] / i * (i - 1);
    return phi;
}

六、秒记口诀 「先质因分解，再乘 (1−1/p)；
筛法遇素数，phi[j]=phi[j]/p*(p-1)」

记住这张图，φ(n) 永远满分！

单点求 φ(n) 的实现要点： 初始 res = n；每找到一个质因子 p，就执行 res = res / p * (p - 1)（即乘上 (1 - 1/p)），并把 p 从 n 中除尽；最后剩下的 n > 1 是最后一个质因子，同样处理。注意”先除后乘”避免溢出。

import java.io.*;
import java.util.StringTokenizer;


public class Main {
    /* 求单个数的欧拉函数 phi(a) */
    static int phi(int a) {
        int res = a;
        for (int i = 2; i <= a / i; i++)
            if (a % i == 0) {          // 找到质因子 i
                res = res / i * (i - 1);
                while (a % i == 0) a /= i;
            }
        if (a > 1) res = res / a * (a - 1);
        return res;
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        StringBuilder out = new StringBuilder();
        while (n-- > 0) {
            int a = Integer.parseInt(br.readLine().trim());
            out.append(phi(a)).append('\n');
        }
        System.out.print(out);
    }
}

线性筛法求欧拉函数#

欧拉函数详解-CSDN博客

import java.io.*;


public class Main {
    static final int N = 1_000_010;
    static int[] primes = new int[N], phi = new int[N];
    static boolean[] st = new boolean[N];
    static int cnt;


    static long getEulers(int n) {
        phi[1] = 1;
        for (int i = 2; i <= n; i++) {
            if (!st[i]) {
                primes[cnt++] = i;
                phi[i] = i - 1;
            }
            for (int j = 0; j < cnt && primes[j] <= n / i; j++) {
                st[primes[j] * i] = true;
                if (i % primes[j] == 0) {
                    phi[primes[j] * i] = phi[i] * primes[j];
                    break;
                } else {
                    phi[primes[j] * i] = phi[i] * (primes[j] - 1);
                }
            }
        }
        long res = 0;
        for (int i = 1; i <= n; i++) res += phi[i];
        return res;
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        System.out.println(getEulers(n));
    }
}

欧拉定理#

欧拉定理（Euler’s Theorem）是数论中最重要的“幂次模”工具之一，一句话先记住：

若整数 a 与正整数 n 互质，则 a^{φ(n)} ≡ 1 (mod n) 其中 φ(n) 是欧拉函数。

一、标准表述 条件：gcd(a, n) = 1 结论：a^{φ(n)} ≡ 1 (mod n)

二、例子验证 n = 10，φ(10) = 4，取 a = 3（gcd(3,10)=1） 3^4 = 81 ≡ 1 (mod 10) ✔

n = 7，φ(7) = 6，任意 a∈{1,2,3,4,5,6} a^6 ≡ 1 (mod 7) ✔（这就是费马小定理）

三、直观理解 把「与 n 互质」的所有剩余看成乘法群 (ℤ/nℤ)^×，它的阶（元素个数）正是 φ(n)。 群论里 Lagrange 定理 ⇒ 任意元素的阶整除群的阶，于是 a^{φ(n)} ≡ 1。

四、常见应用

  1. 模逆元：gcd(a,n)=1 ⇒ a^{-1} ≡ a^{φ(n)-1} (mod n)
  2. 降幂：a^b mod n 可把指数 b 模 φ(n)（再补 φ(n) 防 0）
  3. RSA 加密：解密指数 d 选成 e^{-1} mod φ(n)

欧拉定理的证明#

若整数 aa 与正整数 nn 互质，则

aφ(n)≡1(modn).a^{\varphi(n)} \equiv 1 \pmod{n}.

一、符号与条件

  • gcd⁡(a,n)=1\gcd(a, n) = 1
  • φ(n)\varphi(n)：与 nn 互质且 ≤n\leq n 的正整数个数（欧拉函数）

二、证明（乘积法 / 排列法）

  1. 取出与 nn 互质的全部剩余

    S={r1,r2,…,rφ(n)},1≤ri≤n,gcd⁡(ri,n)=1.S = \{r_1, r_2, \dots, r_{\varphi(n)}\}, \quad 1 \leq r_i \leq n, \quad \gcd(r_i, n) = 1.

  2. 乘以 aa 再模 nn 得到新集合

    aS={ar1 mod n,ar2 mod n,…,arφ(n) mod n}.aS = \{a r_1 \bmod n, a r_2 \bmod n, \dots, a r_{\varphi(n)} \bmod n\}.

  3. aSaS 与 SS 的关系

    • 互质性：gcd⁡(ari,n)=1⇒\gcd(a r_i, n) = 1 \Rightarrow 每个 ari mod na r_i \bmod n 仍 ∈S\in S
    • 互异性：若 ari≡arj(modn)a r_i \equiv a r_j \pmod{n}，则 a(ri−rj)≡0(modn).a(r_i - r_j) \equiv 0 \pmod{n}. 因 gcd⁡(a,n)=1\gcd(a, n)=1，可消去 a⇒ri≡rj(modn)⇒ri=rja \Rightarrow r_i \equiv r_j \pmod{n} \Rightarrow r_i = r_j
      故 aSaS 是 SS 的一个排列。

  4. 两边同时连乘

    ∏i=1φ(n)(ari)≡∏i=1φ(n)ri(modn).\prod_{i=1}^{\varphi(n)} (a r_i) \equiv \prod_{i=1}^{\varphi(n)} r_i \pmod{n}.

  5. 提取公因子 aφ(n)a^{\varphi(n)}

    aφ(n)⋅∏ri≡∏ri(modn).a^{\varphi(n)} \cdot \prod r_i \equiv \prod r_i \pmod{n}.

  6. 消去 ∏ri\prod r_i（因 ∏ri\prod r_i 与 nn 互质，可逆）

    aφ(n)≡1(modn).a^{\varphi(n)} \equiv 1 \pmod{n}.

快速幂#

核心思想：二进制拆分指数。 求 a^k mod p，把指数 k 按二进制拆开：k = 2^0·b0 + 2^1·b1 + …，于是 a^k = a^{b0} · (a²)^{b1} · (a⁴)^{b2} · …。算法维护底数 a 不断自乘（a = a*a % p 得到 a², a⁴, a⁸…），当 k 的当前二进制位为 1 时，把当前底数乘进答案。这样只需要 O(log k) 次乘法，而不是朴素做法的 k 次。

题意#

给定 nn 组 (αi,bi,pi)(\alpha_i, b_i, p_i)，对于每组数据求
αibi mod pi\alpha_i^{b_i} \bmod p_i

输入格式#

第一行一个整数 nn。
接下来 nn 行，每行三个整数 αi,bi,pi\alpha_i, b_i, p_i。

输出格式#

对于每组数据，输出一行结果 αibi mod pi\alpha_i^{b_i} \bmod p_i。

数据范围#

1≤n≤105,1≤αi,bi,pi≤2×1091 \leq n \leq 10^5,\quad 1 \leq \alpha_i, b_i, p_i \leq 2 \times 10^9

import java.io.*;
import java.util.StringTokenizer;


public class Main {
    /* 快速幂：a^k mod p */
    static int qmi(int a, int k, int p) {
        int res = 1 % p;           // 应对 p=1 的情况
        while (k > 0) {
            if ((k & 1) == 1) res = (int) ((long) res * a % p);
            a = (int) ((long) a * a % p);
            k >>= 1;
        }
        return res;
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine().trim());
        while (n-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());
            int p = Integer.parseInt(st.nextToken());
            pw.println(qmi(a, k, p));
        }
        pw.flush();
    }
}

快速幂求逆元#

乘法逆元（Modular Multiplicative Inverse）#

题意#

给定 nn 组 (αi,pi)(\alpha_i, p_i)，其中 pip_i 为质数，求
αi−1 mod pi\alpha_i^{-1} \bmod p_i
即满足
αi⋅x≡1(modpi)\alpha_i \cdot x \equiv 1 \pmod{p_i}
的最小正整数 xx。若逆元不存在，输出 impossible。

输入格式#

第一行一个整数 nn。
接下来 nn 行，每行两个整数 αi,pi\alpha_i, p_i，保证 pip_i 为质数。

输出格式#

对于每组数据输出一行结果：

  • 若 gcd⁡(αi,pi)=1\gcd(\alpha_i, p_i) = 1，输出逆元 xx；
  • 否则输出 impossible。

数据范围#

1≤n≤105,1≤αi,pi≤2×109,pi 为质数1 \leq n \leq 10^5,\quad 1 \leq \alpha_i, p_i \leq 2 \times 10^9,\quad \text{$p_i$ 为质数}

关键公式（费马小定理）#

当 pp 为质数且 gcd⁡(a,p)=1\gcd(a, p) = 1 时， ap−2≡a−1(modp).a^{p-2} \equiv a^{-1} \pmod{p}.

为什么 a^{p-2} 是逆元？ 费马小定理：p 为质数且 a 不被 p 整除时，a^{p-1} ≡ 1 (mod p)。两边同乘 a^{-1} 得 a^{p-2} ≡ a^{-1} (mod p)。所以”求逆元”转化为一次快速幂。注意：若 a % p == 0（即 a 是 p 的倍数），gcd(a,p) ≠ 1，逆元不存在。

import java.io.*;
import java.util.StringTokenizer;


public class Main {
    /* 快速幂：a^k mod p */
    static int qmi(int a, int k, int p) {
        int res = 1 % p;           // 应对 p=1 的情况
        while (k > 0) {
            if ((k & 1) == 1) res = (int) ((long) res * a % p);
            a = (int) ((long) a * a % p);
            k >>= 1;
        }
        return res;
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine().trim());
        while (n-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int p = Integer.parseInt(st.nextToken());
            int res = qmi(a, p-2, p);// 费马小定理：逆元 = a^(p-2) mod p
            if(a % p != 0){// 等价 gcd(a, p) = 1
                pw.println(res);
            }else{
                pw.println("impossible");
            }


        }
        pw.flush();
    }
}

扩展欧几里得算法#

解决的问题： 求不定方程 ax + by = gcd(a, b) 的一组整数解 (x, y)。

推导思路： 递归到边界 b = 0 时，方程变为 a·1 + 0·0 = a，取 x = 1, y = 0。假设下层递归已经解出 bx’ + (a mod b)y’ = g，把 a mod b = a - ⌊a/b⌋·b 代入整理，可得 g = a·y’ + b·(x’ - ⌊a/b⌋·y’)，因此上层解为 x = y’，y = x’ - (a/b)·y’。这就是代码中 x、y 回代两行的来历。

应用： 求逆元（当 gcd(a, m) = 1 时解 ax ≡ 1 (mod m)）、解线性同余方程、中国剩余定理的合并步骤。

题意#

给定 nn 对正整数 (ai,bi)(a_i, b_i)，对于每对数，求出一组 (xi,yi)(x_i, y_i) 使其满足 aixi+biyi=gcd⁡(ai,bi).a_i x_i + b_i y_i = \gcd(a_i, b_i).

输入格式#

第一行一个整数 nn。
接下来 nn 行，每行两个正整数 ai,bia_i, b_i。

输出格式#

共 nn 行，每行输出两个整数 xi,yix_i, y_i（任意合法解均可）。

数据范围#

1≤n≤105,1≤ai,bi≤2×1091 \leq n \leq 10^5,\quad 1 \leq a_i, b_i \leq 2 \times 10^9

import java.io.*;
import java.util.StringTokenizer;


public class Main {
    /* 扩展欧几里得：求 ax + by = gcd(a,b) 的一组解 (x,y)，返回 gcd */
    static long exgcd(long a, long b, long[] xy) {
        if (b == 0) {
            xy[0] = 1; xy[1] = 0;
            return a;
        }
        long g = exgcd(b, a % b, xy);
        long x = xy[0], y = xy[1];
        xy[0] = y;
        xy[1] = x - (a / b) * y;
        return g;
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine().trim());
        while (n-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            long a = Long.parseLong(st.nextToken());
            long b = Long.parseLong(st.nextToken());
            long[] xy = new long[2];
            exgcd(a, b, xy);
            pw.println(xy[0] + " " + xy[1]);
        }
        pw.flush();
    }
}
分享

如果这篇文章对你有帮助，欢迎分享给更多人！

欧拉函数与快速幂
https://blogstella.xyz/posts/数据结构之欧拉函数与快速幂/
作者
Stella
发布于
2026-03-31
许可协议
CC BY-NC-SA 4.0

部分信息可能已经过时

树形DP与记忆化搜索
离散化与区间合并
相关文章 智能推荐
1
质数与筛法
算法 质数的试除法判定、分解质因数、埃氏筛与线性筛、试除法求约数、最大公约数（欧几里得算法）的入门讲解与 Java 实现。
2
线性同余方程与中国剩余定理
算法 线性同余方程 ax ≡ b (mod m) 的求解与中国剩余定理（两两合并法）的入门讲解与 Java 实现。
3
离散化与区间合并
算法 离散化（排序去重 + 二分映射）与区间合并的入门讲解与 Java 实现，处理值域巨大但实际用到的点很少的场景。
4
数位统计与状态压缩DP
算法 数位统计（按位枚举求数字出现次数）与状态压缩 DP（蒙德里安的梦想、最短 Hamilton 路径）的入门讲解与 Java 实现。
5
树形DP与记忆化搜索
算法 树形 DP（没有上司的舞会）与记忆化搜索（最长滑雪轨迹）的入门讲解与 Java 实现。
随机文章 随机推荐
1
KMP算法
算法 2026-03-12
2
DFS和BFS
算法 2026-03-12
3
DP
算法 2026-03-12
4
Writing a Blog Post
Guides 2024-04-01
5
博弈论
算法 2026-03-31
© 2026 Stella. All Rights Reserved. / RSS / Atom / Sitemap
Powered by Astro & Mizuki  Version 9.0

目录