数论工具箱

一、单点拆解的物理边界：试除法与质因数分解

如果给你一个数 $72$，问它是由哪些质数乘出来的，小学生都知道拿短除法去除：先除以 $2$ 得到 $36$，再除以 $2$ 得到 $18$……直到除到只剩 $1$。

这在数学上对应着极其崇高的基石——算术基本定理（唯一分解定理）：

任何一个大于 $1$ 的正整数 $N$，都可以被唯一分解为有限个质数的乘积：

$$N = p_1^{c_1} p_2^{c_2} \cdots p_k^{c_k} \quad (p_1 < p_2 < \dots < p_k \text{ 均为质数}, c_i \ge 1)$$

在竞赛中，面对单点大整数（例如 $N \le 10^{12}$），如果没有现成的质数表，直接上试除法就很方便。

1. 为什么枚举界限只需要到 $\sqrt{N}$？

很多初学者容易死记“循环写到根号 $N$”，但必须想清楚背后的物理事实：

一个整数 $N$ 如果能写成 $a \times b$，那么 $a$ 和 $b$ 不可能同时严格大于 $\sqrt{N}$。一旦都大于 $\sqrt{N}$，它们的乘积必然严格大于 $N$。这意味着：任何一个合数，必然至少包含一个不超过自身平方根的质因子。

因此，我们从最小的质数 $2$ 开始向上枚举因子 $p$。一旦发现 $p$ 能整除当前的数，就用一个 while 循环把它彻底除干净（榨干该质因子的贡献，并统计其指数 $c$）。

核心细节拆解：

• 循环上界动态收缩：条件写成 p <= x / p。这一方面避免了 p * p <= x 在 $x$ 接近 long long 上限时的乘法溢出，另一方面，随着 $x$ 被不断除小，上界也在实时变小，大幅削减无效枚举。
• 为什么不必判断 $p$ 是否为质数？ 比如枚举到 $4$ 时，难道不会把 $4$ 当成质因子放进去吗？绝对不会。因为 $4$ 是 $2$ 的倍数，在 $p=2$ 时，我们已经用 while(x % 2 == 0) x /= 2; 把 $x$ 内部所有的因子 $2$ 彻底抽干了！轮到 $4$ 时，$x$ 根本不可能再被 $4$ 整除。任何合数在轮到它之前，它的所有质因子都已被清空。
• 孤胆英雄：剩下的 $x > 1$ 是什么？ 当 p 超过当前 x / p 跳出循环后，如果剩下的 $x > 1$，它一定是一个质因子！因为若它还是合数，至少还有一个不超过它自身平方根的因子没被除掉，循环就不该结束。如果漏掉这一行判断，分解 $84$ 就会丢失最后的质因子 $7$。

vector<pair<long long, int>> factor(long long x) {
    vector<pair<long long, int>> res;
    for (long long p = 2; p <= x / p; p++) {
        if (x % p != 0) continue;
        int c = 0;
        while (x % p == 0) {
            x /= p;
            c++;
        }
        res.push_back({p, c});
    }
    if (x > 1) res.push_back({x, 1}); // 收下最后剩余的质因子
    return res;
}

该算法的单次时间复杂度为最坏 $O(\sqrt{N})$。对于 $x=1$，返回空表，完全符合 $1$ 既非质数亦非合数的数学定义。

二、约数个数的本质：指数维度的“独立选餐”

拿到 $72$ 的质因数分解：

它的任意一个正约数 $d$，物理上到底是由什么拼出来的？ 显然，它只能由不超过原数所拥有的质因子拼凑而成，即必定具备形态：

此时，决定一个约数的本质，变成了两个独立的单选题：

1. 质因子 $2$ 的指数 $a$ 可以选：$0, 1, 2, 3$（共 $3 + 1 = 4$ 种选法）；
2. 质因子 $3$ 的指数 $b$ 可以选：$0, 1, 2$（共 $2 + 1 = 3$ 种选法）。

根据乘法原理，两个维度的选择互不干扰，组合出来的约数个数恰好是：

我们把这 12 个约数在网格中整整齐齐地铺开：

推广到一般情况，若 $N = p_1^{c_1} p_2^{c_2} \cdots p_k^{c_k}$，则 $N$ 的正约数个数 $d(N)$ 满足：

💡 考场绝杀性质：约数个数的奇偶性 任何一个整数的约数通常都是成对出现的：$d$ 与 $\frac{N}{d}$。 唯独什么时候 $d = \frac{N}{d}$ 会重合？当且仅当 $N$ 是一个完全平方数（此时所有的质因子指数 $c_i$ 均为偶数，导致所有的 $(c_i+1)$ 均为奇数，乘积也必然是奇数）。 结论：$d(N)$ 为奇数 $\iff$ $N$ 是完全平方数。这在许多博弈论或开关灯问题中是瞬间秒题的题眼。

三、从逐个试除到批量剔除：线性筛（欧拉筛）

如果现在的任务变了：不是查单个数字，而是要找出 $1 \sim 10^6$ 范围内的所有质数。

如果依然对每个数跑一次试除法，总时间是 $\sum_{i=1}^N O(\sqrt{i}) \approx O(N\sqrt{N})$。当 $N = 10^6$ 时，运算量达 $10^9$，考场上直接超时暴毙。

1. 埃氏筛的缺陷与线性筛的诞生

埃氏筛 (Sieve of Eratosthenes)：从小到大扫，只要扫到一个没被标记的数 $p$，它就是质数。然后立刻用它去标记所有的倍数 $2p, 3p, 4p\dots$。 虽然我们可以从 $p^2$ 开始标记进行常数优化，但其根本缺陷在于：一个合数会被它的多个质因子反复标记！比如 $30$，在 $p=2$ 时被划掉一次，在 $p=3$ 时又被划掉一次，在 $p=5$ 时还被划掉一次。这造成了大量无效开销，复杂度为 $O(N \log \log N)$。

线性筛（欧拉筛）的核心铁律：

每一个合数，必须且仅被它的“最小质因子”标记一次！

2. 核心代码的一行灵魂：if (i % p == 0) break;

在线性筛中，我们用 $i$ 从 $2$ 枚举到 $N$，并维护一个升序的质数表 primes。内层循环枚举当前已知的所有质数 $p$，将 $i \times p$ 标记为合数。

请紧盯这一行代码：

bad[i * p] = 1;
if (i % p == 0) break; // 灵魂刹车

为什么一旦 i % p == 0 就必须强制跳出？

• 这里的质数 $p$ 是从小到大枚举的。当第一次出现 i % p == 0 时，说明 $p$ 是 $i$ 的最小质因子。
• 如果我们不刹车，继续枚举下一个更大的质数 $q$（$q > p$），接下来被标记的数将是 $v = i \times q$。
• 来看这个新数 $v$ 的质因数结构：因为 $i$ 包含质因子 $p$，所以 $v = i \times q$ 也必然包含质因子 $p$。
• 关键就在这里：$v$ 的质因子中既有 $p$ 又有 $q$，而 $p < q$！这意味着 $v$ 的最小质因子根本不是 $q$，而是 $p$！
• 如果此时让 $(i, q)$ 这一对组合去标记 $v$，就彻底违背了“由最小质因子标记”的原则！这个合数 $v$ 将来必然会在 $i' = \frac{v}{p}$、枚举到素数 $p$ 时被再次标记，从而引发重复计算。

手动追踪一趟，彻底搞懂执行轨迹：

• 当 $i=3$ 时：质数表里有 2, 3。
  • 乘 $p=2$：标记 $3 \times 2 = 6$。$3 \bmod 2 \neq 0$，继续。
  • 乘 $p=3$：标记 $3 \times 3 = 9$。$3 \bmod 3 == 0$，触发 break！停下。
• 当 $i=4$ 时：质数表里有 2, 3。
  • 乘 $p=2$：标记 $4 \times 2 = 8$。$4 \bmod 2 == 0$，触发 break！停下。（绝不去算 $4 \times 3 = 12$）。
• 当 $i=6$ 时：质数表里有 2, 3, 5。
  • 乘 $p=2$：标记 $6 \times 2 = 12$。$6 \bmod 2 == 0$，触发 break！停下。（不会去标记 $6 \times 3 = 18$）。
• 那么刚才没被处理的 $18$ 到底谁来管？
  • 当 $i=9$ 时：乘质数 $p=2$，标记 $9 \times 2 = 18$！$18$ 的最小质因子 $2$ 恰好被放在了质数侧！

没有一个合数会被漏掉，也没有一个合数会被重复标记。每一个数都被精准命中一次，时间复杂度是极其干净利落的 严格 $O(N)$。

3. 完整程序一：筛出所有素数

输入格式：输入一个整数 $n$（$1 \le n \le 10^6$）。
输出格式：第一行输出不超过 $n$ 的素数个数；第二行按升序输出这些素数，两数之间用空格隔开。若无素数则第二行输出空行。
数据范围：$1 \le n \le 10^6$。

样例输入：

20

样例输出：

8
2 3 5 7 11 13 17 19

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

vector<int> primes;
bool bad[N]; // bad[x]=1 表示合数，bad[x]=0 表示素数
int n;

void solve(){
	cin>>n;
	for(int i=2;i<=n;i++){
		if(!bad[i]) primes.push_back(i);
		for(int j=0;j<primes.size();j++){
			int p=primes[j];
			if(p>n/i) break; // 防止 i*p 越过数组上限
			bad[i*p]=1;
			if(i%p==0) break; // 核心：保证每个合数只被最小质因子筛除
		}
	}
	cout<<primes.size()<<'\n';
	for(int i=0;i<primes.size();i++){
		cout<<primes[i]<<(i+1==primes.size()?"":" ");
	}
	cout<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

四、欧拉函数 $\varphi(n)$：容斥计数与在线性筛上的顺手牵羊

1. 什么是欧拉函数？

定义：$\varphi(n)$ 表示在 $1 \sim n$ 的正整数中，与 $n$ 互质（即 $\gcd(x, n) = 1$）的整数个数。
特别约定：$\varphi(1) = 1$（因为 $\gcd(1, 1) = 1$）。

直观例子：$n = 12$ $1 \sim 12$ 中与 $12$ 互质的数有：$1, 5, 7, 11$，共 4 个。所以 $\varphi(12) = 4$。

2. 容斥原理的降维推导

想知道 $1 \sim n$ 中有多少个数和 $n$ 互质，反过来想：排除掉所有与 $n$ 拥有共同质因子的数。

假设 $n$ 只有两个质因子 $p_1, p_2$：

1. 一共有 $n$ 个数；
2. 减去 $p_1$ 的倍数个数：$\frac{n}{p_1}$；
3. 减去 $p_2$ 的倍数个数：$\frac{n}{p_2}$；
4. 加上多减了的公倍数（即 $p_1 p_2$ 的倍数）个数：$\frac{n}{p_1 p_2}$。

全部合起来：

推广到任意一般情况，欧拉函数的计算公式就是如此纯粹与优雅：

⚠️ 避坑提醒：公式里的每一项只取决于“不同的质因子”。$12 = 2^2 \times 3$，虽然有两个 $2$，但也只能乘一次 $(1 - \frac{1}{2})$。

如果单独求单个数的 $\varphi(n)$，只需套用第一节的试除分解质因数板子，每找到一个质因子 $p$，就令 ans = ans / p * (p - 1)（先除后乘防止溢出），复杂度同样是 $O(\sqrt{n})$。

3. 欧拉函数与线性筛的完美合体

如果题目需要我们频繁查询很多数的 $\varphi(x)$（例如 $q = 10^5$ 次询问，每次查 $x \le 10^6$），每次都跑 $O(\sqrt{x})$ 必定会 TLE。

能不能在跑线性筛标质数的同时，顺手把所有数的 $\varphi$ 全部递推出来？

答案是绝对的。回顾线性筛生成新数 $v = i \times p$ 的两种情况，欧拉函数的状态转移顺理成章：

基础基座：$p$ 是质数

显然 $1 \sim p-1$ 的所有数都与 $p$ 互质，故：

分支一：i % p != 0

说明 $p$ 是一个全新登场的质因子，在 $i$ 的质因数分解中从未出现过。 利用积性性质（或者直接看公式：相比 $\varphi(i)$，前面的系数乘了 $p$，右边的连乘项多了一项 $(1 - \frac{1}{p})$）：

分支二：i % p == 0

说明 $p$ 早已经是 $i$ 的质因子之一！ 新生成的数 $i \times p$ 相比原数 $i$，质因数集合没有任何增加，仅仅是质因子 $p$ 的指数加了 $1$。 再看公式：右边的质因子连乘项 $\prod (1 - \frac{1}{p})$ 完全不变！仅仅是前面的总规模系数从 $i$ 变成了 $i \times p$，扩大了 $p$ 倍！因此：

绝妙的契合：这两个分支，分毫不差地对应了线性筛的 if(i % p == 0) 的判断逻辑！我们一行多余的代码都不用加，欧拉函数就已经借着线性筛的东风算好了。

4. 完整程序二：多次查询欧拉函数

输入格式：第一行输入两个整数 $n, q$（$1 \le n \le 10^6, 1 \le q \le 10^5$）；第二行包含 $q$ 个整数 $x$（$1 \le x \le n$）。
输出格式：对每个查询 $x$，输出一行其欧拉函数值 $\varphi(x)$。
数据范围：$1 \le n \le 10^6, 1 \le q \le 10^5$。

样例输入：

12 5
1 2 5 8 12

样例输出：

1
1
4
4
4

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

vector<int> primes;
int phi[N];
bool bad[N];
int n,q;

void solve(){
	cin>>n>>q;
	phi[1]=1; // 物理特判：gcd(1,1)=1
	for(int i=2;i<=n;i++){
		if(!bad[i]){
			primes.push_back(i);
			phi[i]=i-1; // 质数的欧拉函数为 p-1
		}
		for(int j=0;j<primes.size();j++){
			int p=primes[j];
			if(p>n/i) break;
			int v=i*p;
			bad[v]=1;
			if(i%p==0){
				// 分支二：p 已经是 i 的质因子，集合无新增，直接乘 p
				phi[v]=phi[i]*p;
				break;
			}
			// 分支一：p 是全新质因子，根据互质积性转移
			phi[v]=phi[i]*(p-1);
		}
	}
	while(q--){
		int x;
		cin>>x;
		cout<<phi[x]<<'\n';
	}
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

5. 手推追踪：前 12 个数的填表过程

把抽象公式还原到直观表格，看看程序到底怎么流水线式递推：

1. 初始化 $\varphi(1) = 1$。
2. $i=2$：质数，$\varphi(2) = 1$。通过 $2 \times 2$ 命中分支二，直接填好 $\varphi(4) = \varphi(2) \times 2 = 2$。
3. $i=3$：质数，$\varphi(3) = 2$。
   • 乘质数 $2$（分支一）：填好 $\varphi(6) = \varphi(3) \times (2 - 1) = 2$。
   • 乘质数 $3$（分支二）：填好 $\varphi(9) = \varphi(3) \times 3 = 6$。
4. $i=4$：合数，但 $\varphi(4)=2$ 早就被算好了！
   • 乘质数 $2$（分支二）：填好 $\varphi(8) = \varphi(4) \times 2 = 4$。
5. $i=5$：质数，$\varphi(5) = 4$。
   • 乘质数 $2$（分支一）：填好 $\varphi(10) = \varphi(5) \times (2 - 1) = 4$。
6. $i=6$：合数，$\varphi(6)=2$ 已经就绪！
   • 乘质数 $2$（分支二）：填好 $\varphi(12) = \varphi(6) \times 2 = 4$。

不需要在处理 $12$ 时费劲去分解质因数，$12$ 的答案早在前面由较小状态自然流动过来了。这正是算法设计中“空间换时间”与递推思想的极致展现。

五、欧拉定理：同余世界里的周期律与“互质红线”

在快速幂求逆元时，大家都熟背费马小定理：若 $p$ 为质数，且 $\gcd(a, p) = 1$，则 $a^{p-1} \equiv 1 \pmod p$。

但如果模数不是质数，而是一个普通的合数 $m$ 呢？此时接管战局的正是欧拉定理：

若 $m \ge 1$ 且 $\gcd(a, m) = 1$，则：

$$a^{\varphi(m)} \equiv 1 \pmod m$$

1. 指数降维打击

欧拉定理在竞赛中最大的战术价值，就是把天文数字级别的巨大指数拍扁。 只要满足 $\gcd(a, m) = 1$，我们在求 $a^b \bmod m$ 时，就可以理直气壮地对指数取模：

经典实战小例：求 $3^{2026}$ 的个位数。 个位数相当于对模数 $m=10$ 取模。因为 $\gcd(3, 10) = 1$： $\varphi(10) = 10 \times (1 - \frac{1}{2}) \times (1 - \frac{1}{5}) = 4$。 根据欧拉定理，$3^4 \equiv 1 \pmod{10}$。 因此指数可以直接模 $4$：$2026 \bmod 4 = 2$。 答案瞬间化简为 $3^2 \bmod 10 = 9$。

2. 考场高压触电警告：底数与模数不互质！

千万不要把欧拉定理当成“万能指数取模公式”！ 看这个反例：求 $2^4 \bmod 8$。

• 如果有人盲目套公式：$\varphi(8) = 4$，他把指数 $4 \bmod \varphi(8) = 4 \bmod 4 = 0$，得出 $2^0 \equiv 1 \pmod 8$。
• 但事实上，$2^4 = 16 \equiv 0 \pmod 8$！算出来的结果截然相反！

为什么崩溃了？因为 $\gcd(2, 8) = 2 \neq 1$。底数和模数根本不互质，经典欧拉定理在此处完全失效。 教训：在考场上动用指数取模之前，必须先在脑海中拉响最高警报——它们到底互不互质？

六、约数进阶：约数和的物理拼图与 $O(\sqrt{N})$ 提取

1. 约数和的本质：乘法分配律的展开

刚才我们看到，72 的所有约数，都是由不同指数的 2 和 3 组合出来的。 如果我们想把这 12 个约数全部加起来，暴力相加当然可以，但数学上有一种直接打包计算的方法。

请看这个式子：

根据乘法分配律，左边括号里的每一项，都会和右边括号里的每一项相乘一次。这就完美穷举了刚才表格里的所有 12 个组合。 因此，这个乘积的结果，丝毫不差地等于 72 的所有约数之和。

推广到一般情况：对于 $N = p_1^{c_1} p_2^{c_2} \cdots p_k^{c_k}$，其所有正约数之和为：

2. $O(\sqrt{N})$ 提取单个数的所有约数

知道约数个数不够，很多题目要求我们把 $N$ 的所有约数全盘提取出来（比如找最大的真约数）。 既然质因数分解只需要枚举到 $\sqrt{N}$，找约数显然也只需要到 $\sqrt{N}$。

物理推导：约数永远是成对出现的。如果你发现 $i$ 是 $N$ 的约数，那么 $\frac{N}{i}$ 必然也是 $N$ 的约数。这两个约数，必定是一个 $\le \sqrt{N}$，另一个 $\ge \sqrt{N}$。 我们只需用 $i$ 从 1 扫到 $\sqrt{N}$，遇到能整除的，就把 $i$ 和 $\frac{N}{i}$ 一起收入数组中。

细节处理：

1. 当 $N$ 是完全平方数（如 36），枚举到 $i=6$ 时，$\frac{N}{i}$ 也是 6，小心别把它重复添加。
2. 应对 $N \le 10^{12}$ 的大整数时，配对出来的约数完全可能超过 32 位整型上限，必须使用 vector<long long> 来接收！

vector<long long> get_divisors(long long x) {
    vector<long long> res;
    for (long long i = 1; i <= x / i; i++) {
        if (x % i == 0) {
            res.push_back(i);
            if (i != x / i) {
                res.push_back(x / i); // 配对的另一个约数
            }
        }
    }
    return res;
}

七、线性筛的隐藏彩蛋：维护最小质因子实现极速分解

场景痛点：给你 $10^5$ 个数（每个数不超过 $10^7$），让你对每个数做质因数分解。 如果对每个数都跑一遍 $O(\sqrt{N})$ 的试除法，总计算量很大，很容易导致超时。

思路拆解： 还记得线性筛的铁律吗？——每一个合数，都是被它的“最小质因子”标记的。 那我们能不能在线性筛的过程中，顺手把每个数的最小质因子（可以简写为 min_p）记录下来？

有了 min_p 数组，质因数分解就像顺藤摸瓜一样简单，比如要分解 12：

1. 查表 min_p[12] 是 2，记录下 2，让 12 变成 6。
2. 查表 min_p[6] 是 2，记录下 2，让 6 变成 3。
3. 查表 min_p[3] 是 3，记录下 3，让 3 变成 1。分解结束！

整个过程只有查表和除法，单次分解的时间复杂度降到了 $O(\log N)$。

1. 完整程序三：极速多次质因数分解

输入格式：第一行输入两个整数 $M, q$（$2 \le M \le 10^7, 1 \le q \le 10^5$），$M$ 为值域上限；接下来是 $q$ 个待分解的整数 $x$（$2 \le x \le M$）。 输出格式：对每个 $x$，按从小到大的顺序输出其所有的质因子（包含重复的），用空格隔开。 数据范围：$2 \le M \le 10^7, 1 \le q \le 10^5$。

样例输入：

100 3
12
30
98

样例输出：

2 2 3
2 3 5
2 7 7

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

vector<int> primes;
int32_t min_p[N]; // 存最小质因子，最大 10^7。使用 int32_t 避免全局宏导致内存翻倍。

void init_sieve(int limit) {
    for (int i = 2; i <= limit; i++) {
        if (!min_p[i]) {
            min_p[i] = i; // 质数的最小质因子就是自己
            primes.push_back(i);
        }
        for (int j = 0; j < primes.size(); j++) {
            int p = primes[j];
            if (p > limit / i) break;
            min_p[i * p] = p; // 顺手牵羊：i*p 的最小质因子显然是 p
            if (i % p == 0) break;
        }
    }
}

void solve() {
    int m, q;
    cin >> m >> q;
    init_sieve(m);
    
    while (q--) {
        int x;
        cin >> x;
        // O(log x) 顺藤摸瓜式分解
        while (x > 1) {
            cout << min_p[x] << (x == min_p[x] ? "" : " ");
            x /= min_p[x];
        }
        cout << '\n';
    }
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    solve();
    return 0;
}

八、区间筛法入门与起筛位置（选学）

先修要求：熟练掌握埃氏筛原理与基本的时间复杂度概念。

极限场景：求区间 $[L, R]$ 内的素数，其中 $L, R \le 10^{12}$，但区间长度 $R - L \le 10^6$。 既然 $10^{12}$ 的数组开不下，普通筛法没法直接用。

破局思路： 根据第一节的结论，一个合数 $N \le 10^{12}$，其最小质因子一定 $\le \sqrt{N} \le 10^6$。 这意味着，只要我们筛出 $1 \sim 10^6$ 内的素数，就足以作为“武器”，去筛掉 $[L, R]$ 里的所有合数。

我们可以准备一个长度为 $10^6$ 的偏移数组 bool is_prime_range[1000005]，用下标 x - L 来代表真实的数字 $x$。

核心难点：对于每个质因子 $p$，它在 $[L, R]$ 内的第一个倍数在哪里？ 假设 $p=3$，$L=10$，起筛点显然应该是 12。 通用做法是找到不小于 $L$ 的最小的 $p$ 的倍数，这可以通过向上取整得到：在 C++ 中写为 (L + p - 1) / p * p。

但请注意两个关键边界：

1. 如果求出来的倍数就是 $p$ 自己（比如 $L=2, p=3$，算出来起筛点是 3），绝对不能把 $p$ 自己当成合数筛掉。所以起步倍数至少要是 $2p$。
2. 如果区间包含真实数字 0 或 1，必须把它们对应的偏移位置手动划掉，绝不能留下当质数！例如 $L=1$ 时，下标 0 对应数字 1，要划掉；下标 1 对应数字 2，可别误伤。

综合起来，起筛点公式为： long long start = max(2LL * p, (L + p - 1) / p * p);

找到起点后，每次让 start += p，在偏移数组中把对应的 start - L 划掉即可。

九、破除互质红线：扩展欧拉定理（降幂公式）（选学）

在前文我们留下了一个警告：当底数 $a$ 和模数 $m$ 不互质时，欧拉定理会给出错误答案。 但在处理指数塔或大指数模运算时，底数和模数未必互质。此时我们需要用到扩展欧拉定理。

降幂公式： 在不要求 $\gcd(a, m) = 1$ 的情况下，当指数 $b \ge \varphi(m)$ 时：

指数长到读不进整数怎么办？ 把 $b$ 当字符串，从左到右维护两个量：rem 只存模 $\varphi(m)$ 的余数，lim 只存原数与 $\varphi(m)$ 的较小值。每读一位 d，更新 rem=(rem*10+d)%phi、lim=min(phi,lim*10+d)；中间乘法用能装下 10*phi 的类型。读完后，lim==phi 就说明原指数够大，该给 rem 加上一个 phi；否则 lim 就是原指数。不要只看余数判断指数大小。

实战对拍验证： 求 $2^{10} \bmod 12$。 已知 $\varphi(12) = 4$。底数 2 和模数 12 不互质（$\gcd(2, 12) = 2$）。

• 指数 $10 \ge 4$，满足降幂条件。
• 降维后的新指数为：$10 \bmod 4 + 4 = 2 + 4 = 6$。
• 根据公式，应该有 $2^{10} \equiv 2^6 \pmod{12}$。

我们用真实数值验证： $2^{10} = 1024$，而 $1024 \bmod 12 = 4$。 $2^6 = 64$，而 $64 \bmod 12 = 4$。 两者完美吻合。扩展欧拉定理通过“取模后加上 $\varphi(m)$”的修正操作，成功处理了不互质的情况，是处理天文级指数的最终防线。

十、渐进式实战练习与思维对拍

1. 练习一：大整数约数档案

• 题目要求：输入一个整数 $n$（$1 \le n \le 10^{12}$），输出其正约数的个数。
• 输入示例：72 $\to$ 输出：12；输入 36 $\to$ 输出：9；输入 1 $\to$ 输出：1。
• 教练破题指引：单点 $10^{12}$，绝不可用筛法开数组。调用第一节的 factor(n)，从 ans = 1 开始，遍历返回表，每个指数 $c$ 贡献 ans *= (c + 1)。函数已经收下了最后剩余的质因子，不要再乘一次 $2$！只有把试除循环直接写进 main、没有调用 factor 时，才需要自己处理末尾的 x > 1。

2. 练习二：欧拉函数的暴力对拍器

• 题目要求：输入一个整数 $n$（$1 \le n \le 200$）。不使用任何质因数分解或筛法，直接写一层循环枚举 $i \in [1, n]$，统计有多少个 $i$ 满足 __gcd(i, n) == 1，输出该计数。
• 教练破题指引：线性筛欧拉函数的转移分支容易在考场紧张时写反。把这个 $O(n \log n)$ 暴力和筛法对照，先穷举 $n \in [1,200]$，就能抓出不少小错误。对拍怎么组织，见《综合建模与赛场调试》·对拍。

3. 深度反思提问

1. 为什么 $\varphi(13) = 12$，但我们绝不能推论出“所有小于 $13$ 的正整数都是质数”？
2. 同样是对 $n$ 跑一遍质因数分解，为什么一份分解结果，既能被拿去算约数个数，又能被拿去算欧拉函数？二者对指数的处理方式有何本质不同？
   • （提示：约数关注的是指数的每一次独立选取；而欧拉函数关注的是质因子对互质比例的剔除，指数多大不影响被排除的比例）。