Euler φ 函数与 Möbius 反演在组合数论中的应用是什么？
Euler φ(n) 表示 1..n 中与 n 互素的整数个数，是积性函数，可用于计数互素对、求环的乘法群阶数。Möbius 函数 μ(n) 是积性函数，μ(1)=1，μ(p)=−1，μ(p^k)=0（k≥2）。Möbius 反演：若 f(n) = Σ_{d|n} g(d)，则 g(n) = Σ_{d|n} μ(d)·f(n/d)。它常用来求互素计数：如 Σ_{i=1}^n Σ_{j=1}^n [gcd(i,j)=1] 可用 Σ_{d|n} μ(d) 的公式化简，或统计"恰好等于某值的计数"。
Möbius 反演与 Dirichlet 卷积结合，是组合数论中"从倍数的计数还原互素的计数"的标准工具，与 φ 的互素计数互补。
线性筛求最小质因子（spf）为什么每个合数只被最小质因子筛一次，如何用 spf 实现 O(log n) 质因数分解？
线性筛（欧拉筛）维护 spf[x]（x 的最小质因子）。遍历每个数 x 和已筛出的素数 p，当 p ≤ spf[x] 时标记 x·p 的 spf 为 p。这样每个合数 x·p 只被其最小质因子 p 筛一次（因为 p 是 x·p 的最小质因子，且遍历 p 到 spf[x] 即停，避免更大的素数重复标记）。因此每个数入表一次，总复杂度 O(n)。用 spf 分解：不断取 n 的 spf 并除以它，每次除以最小质因子，约 O(log n) 次（若重复因子则需 log 次），得到质因数分解。
线性筛的"只被最小质因子筛一次"保证 O(n) 复杂度，spf 数组同时支持 O(log n) 质因数分解，是一举两得。
int[] spf = new int[n + 1];
List<Integer> primes = new ArrayList<>();
for (int i = 2; i <= n; i++) {
if (spf[i] == 0) { spf[i] = i; primes.add(i); }
for (int p : primes) {
if (p > spf[i] || i * p > n) break;
spf[i * p] = p;
}
}
// O(log n) 分解
Map<Integer,Integer> fac = new HashMap<>();
while (x > 1) { int c = spf[x]; fac.merge(c, 1, Integer::sum); x /= c; }
埃氏筛的复杂度为什么是 O(n log log n)，从每个素数 p 标记 n/p 个倍数求和推导？
埃氏筛对每个素数 p 标记其所有倍数，素数 p 标记 n/p 个倍数。总标记数 Σ_{p≤n} n/p = n·Σ_{p≤n} 1/p。由 Mertens 定理，Σ_{p≤n} 1/p ≈ ln ln n + M（M 为常数），故总复杂度 O(n log log n)。朴素实现从每个 p 的倍数开始标记，最终 O(n log log n)；若从 p^2 开始标记可进一步减少常数，但渐近不变。
复杂度关键来自"素数倒数和 ≈ ln ln n"这一数论事实，把 n 次遍历映射为 n log log n。
Atkin 筛（用二次型筛）的优势与边界是什么？
Atkin 筛利用二次形式的模分类：素数 p 的某些性质（如 p mod 4、p mod 12 等）与二次同余 p ≡ x² + y² 等可解性相关，从而用模运算直接判定素数，跳过大量合数。其复杂度约 O(n/log log n)，比埃氏筛的 O(n log log n) 更优，常数也小。但实现复杂、缓存不友好、对 n 很大时优势边际递减，且现代实现（如 libdivide、分段筛）常让埃氏筛在工程上更有竞争力。Atkin 筛优势在理论复杂度，边界是工程复杂度高、常数未必小。
Atkin 筛展示了"用二次型数论减少无效标记"的思路，但工程上常被经过优化的分段埃氏筛超越。
线性筛（Euler sieve）的 O(n) 时间复杂度如何证明？
线性筛保证每个合数恰好被其最小质因子筛一次。证明：对每个合数 m = p·q，其中 p 是 m 的最小质因子，q = m/p。在外层循环处理到 q 时，已筛出的素数中包含 p（且 p ≤ spf[q]），于是 i·p = m 会被标记，且由于遍历到 p=spf[q] 即 break，不会用更大的素数标记 m。因此 m 只被 p 标记一次。每个数 i 被访问一次，且其内层循环的 break 保证总操作数 O(n)。
O(n) 的关键是"每个合数单一最小质因子 + break 提前终止"，保证每个操作都对应一个唯一的合数或素数。
Carmichael λ 如何分段计算？λ(p^k) 与 λ(2^k) 有什么特例（k≥3 时减半），如何由分解结果求整体 λ(n)？
Carmichael λ(n) 是使 a^λ(n) ≡ 1 (mod n) 对所有与 n 互素的 a 成立的最小正整数。对素数幂：λ(p^k) = φ(p^k) = p^{k-1}(p-1)（p 为奇素数）；λ(2) = 1，λ(4) = 2，λ(2^k) = 2^{k-2}（k≥3，即 φ(2^k) 减半，因为 2^k 的乘法群不是循环群）。对 n 的分解 n = ∏ p_i^{k_i}，整体 λ(n) = lcm(λ(p_i^{k_i}))（各素数幂的 λ 的最小公倍数）。
λ 与 φ 的区别在于 2^k 特例和取 lcm 而非相乘，这反映了乘法群结构（Carmichael 函数是群公示数的最小公倍数）。
用扩展欧拉定理降幂时，b 巨大时 a^b mod m 如何按 b 与 φ(m) 的大小关系分支处理？
扩展欧拉定理：若 gcd(a, m) = 1，则 a^b ≡ a^{b mod φ(m)} (mod m)。若 gcd(a, m) ≠ 1，则当 b ≥ φ(m) 时 a^b ≡ a^{b mod φ(m) + φ(m)} (mod m)；当 b < φ(m) 时直接计算 a^b。因此降幂需按 b 与 φ(m) 的大小关系分支：若 b 比 φ(m) 小，直接算；若 b ≥ φ(m)，指数取 b mod φ(m) + φ(m)。这使 b 巨大无法直接计算时也能高效求幂。
分支的根据是"指数是否达到 φ(m)"，避免在 a 与 m 不互素时错误地只取 b mod φ(m)。
long modPow_phi(long a, long b, long m) {
long phi = eulerPhi(m);
long exp = (b >= phi) ? b % phi + phi : b; // 分支
return fastPow(a, exp, m);
}
Stripping Lemma 在区间素数筛（分段筛）的工程应用是什么？
Stripping Lemma 泛指"逐步剥离因子/合数"的技巧，在区间素数筛中体现为分段筛：先筛出 ≤ √R 的素数，然后用这些素数去标记区间 [L, R] 内的合数，一次剥离一个素数因子的倍数。因为只需 √R 以内的素数预筛，区间内每个数被其素因子剥离，复杂度 O((R-L+1)·log log R + √R)。分段筛让巨大区间也能在受限内存内筛素数。
分段筛把"全局筛"拆成"预筛小素数 + 局部标记"，是 Stripping 逐层剥离思想在工程上的应用，突破内存上限。
Carmichael λ 在 PKCS#1 v2.2 的 RSA-CRT 工程应用是什么？
PKCS#1 v2.2 的 RSA 私钥使用 λ(n) 而非 φ(n) 来定义私钥指数 d：d ≡ e^{-1} (mod λ(n))，其中 λ(n) = lcm(p-1, q-1)。因为 λ(n) 是使 a^λ(n) ≡ 1 (mod n) 的最小指数，用 λ 而非 φ 能给出更小的合法 d，且保证加密/解密互逆。RSA-CRT 仍用 p、q、dP、dQ、qInv 加速解密，但密钥指数 d 的定义基于 λ(n)。这是 PKCS#1 v2.2 的规范做法。
用 λ(n) 定义 d 是标准演化，反映 Carmichael 函数刻画乘法群结构的精确性，同时保证 e·d ≡ 1 (mod λ(n)) 的最小指数。
Euler φ 函数在乘法群 (Z/nZ)* 的阶数与群论意义是什么？
(Z/nZ)* 是模 n 的既约剩余类全体（与 n 互素的元素）构成的乘法群，其阶恰好等于 φ(n)。这个群是有限交换群，其结构由 n 的分解决定。φ(n) 作为群阶，是欧拉定理（a^φ(n) ≡ 1）和原根存在性（当且仅当 n = 2, 4, p^k, 2p^k 时 (Z/nZ)* 是循环群）的基础。群论上，φ(n) 决定了该群的可能子群结构，也决定了离散对数所在的群大小。
φ(n) 的定义本身即"与 n 互素的数的个数"，与乘法群阶精确对应，是数论与群论的桥梁。
欧拉 φ 函数与 Carmichael λ 函数的定义差异与关系是什么？
φ(n) 是 1..n 中与 n 互素的整数个数，即 (Z/nZ)* 的阶。λ(n) 是使 a^λ(n) ≡ 1 (mod n) 对一切与 n 互素的 a 成立的最小正整数，即群 (Z/nZ)* 的幺元指数（exponent）。关系：λ(n) 整除 φ(n)（λ 是群的指数，必整除群阶 φ(n)），且 λ(n) 通常远小于 φ(n)。对素数 n，两者相等（φ(p)=λ(p)=p-1）。
φ 是"群的阶"，λ 是"群的幺元指数"，前者是卡迈克尔函数的倍数，后者刻画每个元素的最小消去指数。
欧拉定理与 Carmichael 定理在 RSA、原根判定中的典型应用是什么？
欧拉定理 a^φ(n) ≡ 1 (mod n)（gcd(a,n)=1）是 RSA 正确性的基础：由 ed ≡ 1 (mod φ(n))（或 λ(n)），得 a^{ed} ≡ a (mod n)，保证解密还原。Carmichael 定理用更小的 λ(n) 给出同样的结论，因此 RSA 用 ed ≡ 1 (mod λ(n)) 也能工作且更紧凑。原根判定中，g 是 (Z/nZ)* 的原根当且仅当 g 的阶等于 φ(n)，且对 φ(n) 的每个素因子 q，g^{φ(n)/q} ≢ 1 (mod n)。用 λ 或 φ 均可判定。
欧拉定理给出"指数为 φ(n) 时全为 1"，Carmichael 把指数收紧到 λ(n)；两者都支撑 RSA 的加解密互逆与原根阶判定。
计算欧拉 φ 有哪些常见误区（分解质因数、特殊情况）？
常见误区：① 错误地认为 φ(n) = n-1 对任意 n 成立（只有 n 为素数时才成立）；② 求积时漏掉重复质因子（正确公式 φ(n) = n·∏_{p|n}(1-1/p) 对每个不同质因子只乘一次）；③ 忽略 φ(1)=1、φ(2)=1 等特殊情况；④ 忘记 φ 的积性只在互素时成立（φ(a·b)=φ(a)φ(b) 需 gcd(a,b)=1）；⑤ 对质因子幂 p^k，φ(p^k) = p^k - p^{k-1} = p^{k-1}(p-1)，而非 p^k-1。
φ 计算的关键是"正确分解质因数 + 每个不同质因子只算一次 + 处理幂形式"，这些细节是常见出错点。
long phi(long n) {
long res = n;
for (long p = 2; p * p <= n; p++) {
if (n % p == 0) {
while (n % p == 0) n /= p;
res -= res / p; // res = res * (1 - 1/p)
}
}
if (n > 1) res -= res / n;
return res;
}
线性筛（欧拉筛）的原理是什么，为什么每个合数恰好被其最小质因子筛除一次？
线性筛对每个数 i，遍历已筛出的素数 p，标记 i·p 的 spf 为 p，当 p 超过 i 的最小质因子 spf[i] 时 break。对任意合数 m = s·p（p 为 m 的最小质因子，s = m/p），在遍历到 s 时，p 已在素数表中且 p ≤ spf[s]，所以 m 会被 p 标记；又因为 p 是 m 的最小质因子，遍历到 p 后即 break，更大的素数不会标记 m。因此每个合数恰好被其最小质因子筛一次，操作数 O(n)。
"break 条件 p ≤ spf[i]" 保证每个合数只对应一次标记，是线性筛 O(n) 的核心。
区间筛（分段筛）如何求 [L,R] 内所有素数？为什么只需预筛 √R 以内的素数，标记区间时的偏移映射是什么？
区间筛：先用普通筛筛出 ≤ √R 的所有素数；然后对每个素数 p，在区间 [L,R] 内找到第一个 p 的倍数（≥ L），从该点开始标记 p 的倍数，起始位置用 (L + p - 1)/p·p 或 L - (L mod p) 计算。只需 √R 内的素数，因为区间 [L,R] 内任意合数必有 ≤ √R 的素因子（若合数 m 的所有素因子都 > √R，则 m > R，矛盾）。标记时用偏移 i-L 映射到数组下标，避免为整个大区间开数组。
"合数必有 ≤ √R 的素因子"是只需预筛 √R 内素数的理论依据，偏移映射让每个数的标记用相对下标，省内存。
boolean[] comp = new boolean[R - L + 1];
for (int p : primes) { // primes ≤ √R
long start = Math.max((long) p * p, ((L + p - 1) / p) * (long) p);
for (long j = start; j <= R; j += p) comp[(int)(j - L)] = true;
}
欧拉 φ 函数的性质是什么？积性、p^k 情形与快速求解如何？
φ 是积性函数：gcd(a,b)=1 时 φ(ab)=φ(a)φ(b)。对素数幂 p^k，φ(p^k) = p^{k-1}(p-1)。由积性和素因子分解 n = ∏ p_i^{k_i}，φ(n) = ∏ φ(p_i^{k_i}) = ∏ p_i^{k_i-1}(p_i-1) = n·∏(1-1/p_i)。快速求解：对单个数用试除分解质因数 O(√n)；对 1..n 全部值用线性筛 O(n) 递推（利用积性，每个数由最小质因子更新）。
积性 + 素数幂公式是 φ 的一切计算基础，单个数 O(√n)、批量 O(n) 是两种典型快速求解。
如何在筛质数时同步计算 1..n 的所有 φ 值？
线性筛同步计算 φ：对每个数 i，φ[1]=1。若 i 是素数，φ[i] = i-1。由递推：若 i 是最小质因子 p 的倍数，则 φ[i·p] = φ[i]·p（p 已出现）；否则 φ[i·p] = φ[i]·(p-1)（p 首次出现，利用积性）。在筛 i·p 时根据 p 是否等于 spf[i] 选择乘 p 或乘 p-1。这样在 O(n) 内得到所有 φ 值。
利用积性，根据 p 是否是最小质因子首现决定乘 p 或 p-1，与线性筛同步完成，O(n) 全量 φ。
int[] phi = new int[n + 1];
phi[1] = 1;
for (int i = 2; i <= n; i++) {
if (spf[i] == 0) { spf[i] = i; primes.add(i); phi[i] = i - 1; }
for (int p : primes) {
if (p > spf[i] || i * p > n) break;
spf[i * p] = p;
phi[i * p] = (p == spf[i]) ? phi[i] * p : phi[i] * (p - 1);
}
}
欧拉定理与 Carmichael 函数 a^φ(n)≡1 与 a^λ(n)≡1 的应用差异是什么？
欧拉定理 a^φ(n) ≡ 1 对所有与 n 互素的 a 成立，是 RSA 的基础，但 φ(n) 较大。Carmichael 定理 a^λ(n) ≡ 1 使用更小的 λ(n)（整除 φ(n)），是"最小"指数。应用差异：RSA 中 ed ≡ 1 (mod φ(n)) 或 (mod λ(n)) 都正确，但用 λ(n) 得到更小的 d，密钥更紧凑；Carmichael 常用于求最小化指数、刻画原根、以及需要精确最小指数的场合。凡 φ 可用之处 λ 也适用（因 λ | φ），但 λ 更精确。
λ 是 φ 的整除因子，两者都满足"指数为 1"的幂等性质，但 λ 给出最小指数，是更精确的刻画。
线性筛与欧拉函数：如何在筛素数时同步计算 φ 值？
与问题 17 同理，线性筛在确定每个数的最小质因子 spf[i] 的同时，按积性递推 φ：φ[1]=1；i 为素数时 φ[i]=i-1；对 i·p，若 p 等于 spf[i]（即 p 已作为因子出现），则 φ[i·p] = φ[i]·p；否则 φ[i·p] = φ[i]·(p-1)。由于线性筛每个数只处理一次，总体 O(n) 计算全部 φ 值。
结构上复用问题 17 的递推，是"筛一次同时得到素数与 φ 值"的经典做法，O(n) 完成。
素数定理 π(n) ≈ n/ln n 如何指导筛法上限与 Miller-Rabin 随机候选的期望步数？
素数定理 π(n) ≈ n/ln n 给出素数密度。筛法上限：若想筛出第 k 个素数，由 π(n) ≈ n/ln n 知需取 n ≈ k·ln k（约 n 个整数中含 k 个素数），故筛法上限取 n = k·(ln k + ln ln k) 量级。对 Miller-Rabin，随机选一个 n 附近的奇数，其为素数的概率约 2/ln n（奇数中密度翻倍），故期望需试约 (ln n)/2 个候选才能遇到素数；利用此可估计随机生成大素数所需迭代次数。
素数定理把"素数分布"转化为"密度估计"，指导筛法规模与随机素性候选的期望步数，是渐进分析的实用工具。