整除、因数、倍数、指数、质（素）数、合数

一、概念解析

初等数论

初等数论是信奥赛普及组的核心知识点，涉及整数的基本性质和运算规律。

概念解析

1. 整除

• 定义：若整数 $a$ 除以整数 $b$（$b \neq 0$）的商为整数且无余数，则称 $b$ 整除 $a$，记为 $b \mid a$（如 $2 \mid 6$，因 $6 \div 2 = 3$ 是整数）。
• 性质：
  • 若 $b \mid a$ 且 $c \mid b$，则 $c \mid a$（传递性）；
  • 若 $b \mid a$ 且 $b \mid c$，则 $b \mid (a \pm c)$（加减性）；
  • 若 $b \mid a$，则 $b \mid k \cdot a$（$k$ 为整数，倍数性）。

2. 因数与倍数

• 因数：若 $b \mid a$，则 $b$ 是 $a$ 的因数（约数），如6的因数有1,2,3,6。
• 倍数：若 $b \mid a$，则 $a$ 是 $b$ 的倍数，如6是2、3的倍数。
• 关系：因数与倍数相互依存，一个数的因数个数有限，倍数个数无限。

3. 指数（乘方）

• 定义：$a^n$ 表示 $n$ 个 $a$ 相乘（$a$ 为底数，$n$ 为指数，$n \geq 1$），如 $2^3 = 2 \times 2 \times 2 = 8$。
• 运算性质：
  • $a^m \cdot a^n = a^{m+n}$；
  • $(a^m)^n = a^{m \cdot n}$；
  • $a^m \div a^n = a^{m-n}$（$m > n$ 且 $a \neq 0$）。

4. 质数与合数

• 质数（素数）：大于1的自然数，除了1和自身外无其他因数（如2,3,5,7），2是唯一的偶质数。
• 合数：大于1的自然数，除了1和自身外还有其他因数（如4,6,8,9）。
• 特殊说明：1既不是质数也不是合数。

二、实战案例

实战案例

案例1：判断整除与求因数

问题：输入整数 $n$，输出其所有正因数（要求从小到大排列）。

c++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> factors;
    
    // 枚举到sqrt(n)，避免重复计算
    for (int i = 1; i * i <= n; ++i) {
        if (n % i == 0) { // i是n的因数
            factors.push_back(i);
            if (i != n / i) { // 避免i和n/i相等时重复添加（如n=4，i=2）
                factors.push_back(n / i);
            }
        }
    }
    
    sort(factors.begin(), factors.end()); // 排序
    
    for (int f : factors) {
        cout << f << " ";
    }
    return 0;
}

关键点：通过枚举到 $(\sqrt{n})$ 优化因数查找，时间复杂度为 $(O(\sqrt{n}))$，避免枚举到 $(n)$ 的低效性。

案例2：质数判断（试除法优化）

问题：输入整数 $n$，判断其是否为质数。

c++

#include <iostream>
#include <cmath>
using namespace std;

bool isPrime(int n) {
    if (n <= 1) return false; // 1不是质数
    if (n == 2) return true; // 2是质数
    if (n % 2 == 0) return false; // 偶数一定不是质数（除2外）
    
    // 只枚举奇数，且到sqrt(n)
    for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

int main() {
    int n;
    cin >> n;
    if (isPrime(n)) {
        cout << "是质数" << endl;
    } else {
        cout << "不是质数" << endl;
    }
    return 0;
}

关键点：优化试除法，排除偶数和1，仅枚举奇数到 $(\sqrt{n})$，时间复杂度降至 $(O(\sqrt{n}/2))$，适合普及组数据范围（$n \leq 10^9$）。

案例3：快速幂（指数运算优化）

问题：计算 $a^b \mod m$（避免大指数直接计算导致的溢出）。

c++

#include <iostream>
using namespace std;

// 快速计算 (a^b) % m
long long fastPow(long long a, long long b, long long m) {
    long long res = 1;
    a %= m; // 防止a过大
    while (b > 0) {
        if (b % 2 == 1) { // 若当前指数为奇数，乘上当前a
            res = (res * a) % m;
        }
        a = (a * a) % m; // 底数平方
        b /= 2; // 指数减半
    }
    return res;
}

int main() {
    long long a, b, m;
    cin >> a >> b >> m;
    cout << fastPow(a, b, m) << endl;
    return 0;
}

关键点：快速幂通过“指数减半，底数平方”将时间复杂度从 $(O(b))$ 降至 $(O(\log b))$，解决大指数（如 $b = 10^9$）的计算问题，避免溢出。

案例4：埃氏筛法（批量求质数）

问题：输出1~n中的所有质数（$n \leq 10^6$）。

c++

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<bool> isPrime(n + 1, true); // 标记是否为质数
    isPrime[0] = isPrime[1] = false; // 0和1不是质数
    
    // 埃氏筛：从2开始，标记其倍数为非质数
    for (int i = 2; i * i <= n; ++i) {
        if (isPrime[i]) { // 若i是质数，标记其倍数
            for (int j = i * i; j <= n; j += i) { // 从i*i开始，避免重复标记
                isPrime[j] = false;
            }
        }
    }
    
    // 输出所有质数
    for (int i = 2; i <= n; ++i) {
        if (isPrime[i]) {
            cout << i << " ";
        }
    }
    return 0;
}

关键点：埃氏筛通过“标记质数的倍数”高效批量筛选质数，时间复杂度约为 $(O(n \log \log n))$，适合 $(n \leq 10^6)$ 的场景。

三、信奥赛应用场景

信奥赛应用场景

1. 质数相关问题：

   • 质数判断（如“统计1~n中的质数个数”）；
   • 质因数分解（如“将n分解为质因数乘积”，是求最大公约数、最小公倍数的基础）；
   • 素数筛法（如“找出n以内的所有质数”，埃氏筛是普及组常用算法）。

2. 因数与倍数问题：

   • 因数个数/和（如“计算n的所有因数之和”，需结合因数分解）；
   • 最大公约数（gcd）与最小公倍数（lcm）（如“求两个数的gcd”，用辗转相除法）；
   • 倍数枚举（如“找出1~n中能被3或5整除的数的和”）。

3. 指数运算问题：

   • 模运算（如“计算 $(a^b \mod m)$”，快速幂是核心工具）；
   • 大指数化简（如“判断 $(2^{100})$ 的末位数字”，利用周期规律）。

四、避坑指南

避坑指南

1. 整数溢出：

   • 陷阱：计算因数乘积（如 $(i \times i)$）或指数运算（如 $(a^b)$）时，结果超过 int 范围（$(2 \times 10^9)$）。
   • 解决：用 long long 存储中间结果；模运算中及时取模（如快速幂中的 res = (res * a) % m）。

2. 质数判断边界错误：

   • 陷阱：遗漏 $(n=2)$（唯一偶质数）或误判1为质数。
   • 解决：优先处理特殊值（$(n \leq 1)$ 直接返回 false，$(n=2)$ 返回 true）。

3. 因数枚举重复：

   • 陷阱：枚举因数时，对平方数（如4=2×2）重复添加因数（如添加2两次）。
   • 解决：判断 $i \neq n/i$ 时才添加 $n/i$（如案例1）。

4. 埃氏筛范围错误：

   • 陷阱：筛法中循环终止条件错误（如用 $i \leq n$ 而非 $i \times i \leq n$），导致效率低下。
   • 解决：外层循环到 $\sqrt{n}$ 即可，因更大的数若未被标记，必为质数。

重要

• 核心地位：整除、质数、因数等概念是初等数论的基础，在信奥赛普及组中直接考察（如质数判断、因数计算）或作为工具支撑其他问题（如gcd、快速幂）。
• 算法要点：掌握试除法（质数判断、因数查找）、快速幂（指数模运算）、埃氏筛（批量质数筛选）等核心算法，理解其时间复杂度优化逻辑。
• 竞赛提示：普及组数论题注重基础实现，需注意边界条件（如1、2的特殊性）和数据范围（用 long long 防溢出），熟练运用“枚举到 $\sqrt{n}$”“及时取模”等技巧，避免因细节错误丢分。

取整

一、概念解析

取整

取整是初等数论中处理整数与非整数关系的基础操作，在编程中用于将非整数转化为整数。

常见取整方式

1. 常见取整方式

• 向下取整（Floor）：
  定义：取不大于目标数的最大整数（向负无穷方向取整）。
  例：$(\lfloor 3.8 \rfloor = 3)$，$(\lfloor -2.3 \rfloor = -3)$。
  C++实现：floor(x)（需包含 <cmath>，返回 double 类型）。

• 向上取整（Ceil）：
  定义：取不小于目标数的最小整数（向正无穷方向取整）。
  例：$(\lceil 3.2 \rceil = 4)$，$(\lceil -2.7 \rceil = -2)$。
  C++实现：ceil(x)（需包含 <cmath>，返回 double 类型）。

• 四舍五入（Round）：
  定义：根据小数部分大小，向最接近的整数取整（若小数部分为0.5，则向远离0的方向取整）。
  例：$(\text{round}(3.4) = 3)$，$(\text{round}(3.5) = 4)$，$(\text{round}(-2.5) = -3)$。
  C++实现：round(x)（需包含 <cmath>，返回 long 或 double，取决于编译器）。

• 截断取整（Truncate）：
  定义：直接去掉小数部分（向0方向取整）。
  例：(int)3.8 = 3，(int)-2.3 = -2。
  C++实现：直接强制类型转换（(int)x），仅保留整数部分。

2. 整数除法的取整特性

C++中整数除法（a / b，a和b为整数）默认采用向零取整：

• 正数除法：与向下取整一致（如 5 / 2 = 2，等同于 $(\lfloor 5/2 \rfloor = 2)$）。
• 负数除法：结果向0靠拢（如 -5 / 2 = -2，不同于向下取整的 -3）。

二、实战案例

实战案例

案例1：四种取整方式对比

问题：对不同数值应用四种取整方式，观察结果差异。

c++

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    double x = 3.8, y = -2.3;
    
    // 向下取整
    cout << "floor(3.8) = " << floor(x) << endl;       // 3
    cout << "floor(-2.3) = " << floor(y) << endl;     // -3
    
    // 向上取整
    cout << "ceil(3.8) = " << ceil(x) << endl;        // 4
    cout << "ceil(-2.3) = " << ceil(y) << endl;       // -2
    
    // 四舍五入
    cout << "round(3.8) = " << round(x) << endl;      // 4
    cout << "round(-2.3) = " << round(y) << endl;     // -2
    
    // 截断取整（强制类型转换）
    cout << "(int)3.8 = " << (int)x << endl;          // 3
    cout << "(int)-2.3 = " << (int)y << endl;         // -2
    
    return 0;
}

关键点：通过对比可见，不同取整方式对正负数值的处理逻辑差异，尤其是负数的向下取整与截断取整结果不同。

案例2：整数除法的向上取整实现

问题：对于正整数 a 和 b，计算 a / b 的向上取整结果（如 5 / 2 = 3，4 / 2 = 2）。

c++

#include <iostream>
using namespace std;

// 正整数a/b的向上取整：(a + b - 1) / b
int ceilDiv(int a, int b) {
    return (a + b - 1) / b;
}

int main() {
    cout << ceilDiv(5, 2) << endl;  // 3（5/2=2.5，向上取整为3）
    cout << ceilDiv(4, 2) << endl;  // 2（4/2=2，向上取整为2）
    cout << ceilDiv(7, 3) << endl;  // 3（7/3≈2.333，向上取整为3）
    return 0;
}

原理：利用整数除法向零取整的特性，通过 a + b - 1 使分子“进位”，再除以 b 得到向上取整结果（仅适用于正整数）。

案例3：四舍五入的手动实现

问题：手动实现对小数 x 保留 n 位小数的四舍五入（如 x=3.14159，n=2 时结果为 3.14）。

c++

#include <iostream>
#include <cmath>
using namespace std;

// 保留n位小数的四舍五入
double roundN(double x, int n) {
    double power = pow(10, n);  // 10的n次方
    return round(x * power) / power;
}

int main() {
    cout << roundN(3.14159, 2) << endl;  // 3.14
    cout << roundN(3.14559, 2) << endl;  // 3.15（第3位是5，进1）
    cout << roundN(9.999, 2) << endl;    // 10.00
    return 0;
}

关键点：通过放大 10^n 倍后四舍五入，再缩小回原尺度，实现指定小数位数的精确取整。

三、信奥赛应用场景

信奥赛应用场景

1. 分配问题：
   如“将 n 个物品分给 k 个人，每人至少1个，求最多的人至少分到几个”，需用向上取整 (n + k - 1) / k。

2. 范围计算：
   如“已知正方形面积 s，求边长的最小整数（向上取整）”，即 ceil(sqrt(s))。

3. 精度处理：
   如“计算平均分并保留1位小数”，需用四舍五入 round(score * 10) / 10。

4. 循环控制：
   如“将数组按 k 个元素一组分割，求组数”，需向上取整 (n + k - 1) / k。

四、避坑指南

避坑指南

1. 负数取整陷阱：

   • 陷阱：对负数使用 (a + b - 1) / b 求向上取整（如 -5 / 2 期望结果为 -2，但公式计算为 (-5 + 2 - 1)/2 = -4/2 = -2，看似正确；但 -4 / 2 会得到 (-4 + 2 - 1)/2 = -3/2 = -1，实际应为 -2）。
   • 解决：负数向上取整需单独处理，或直接使用 ceil((double)a / b)。

2. 浮点数精度误差：

   • 陷阱：floor(3.9999999999) 因精度问题可能返回 2（极少发生，但需注意）。
   • 解决：对精度敏感场景，可先加一个极小值（如 1e-8）再取整，如 floor(x + 1e-8)。

3. 整数除法方向混淆：

   • 陷阱：误认为 (-5) / 2 结果为 -3（实际C++中为 -2，向零取整）。
   • 解决：处理负数除法时，明确取整方向，必要时用 floor 或 ceil 函数。

4. 强制类型转换的风险：

   • 陷阱：(int)round(x) 中，round 返回 double 类型，当 x 过大时可能超出 int 范围导致溢出。
   • 解决：大数值取整时用 long long 接收，如 (long long)round(x)。

重要

• 核心作用：取整是连接整数与非整数计算的桥梁，在分配、精度控制、范围判断等场景中必不可少。
• 使用原则：根据需求选择取整方式（向下/向上/四舍五入），正整数向上取整优先用 (a + b - 1) / b 提升效率，负数和浮点数取整优先用 <cmath> 库函数保证正确性。
• 竞赛提示：普及组中取整问题多隐藏在实际场景中（如分组、分配），需重点注意负数处理和精度误差，避免因取整方向错误导致逻辑漏洞。

模运算与取余

一、概念解析

模运算（Modulo Operation）与取余（Remainder）

模运算（Modulo Operation）与取余（Remainder）是处理整数除法余数的两种运算，在编程中常被混用，但数学定义存在细微差异，核心概念如下：

概念解析

1. 基本定义

• 通用计算步骤：
  对于整数 $a$（被除数）和非零整数 $b$（除数），均需找到整数 $q$（商）和 $r$（结果），满足：
  $a = b \times q + r \quad \text{且} \quad 0 \leq |r| < |b|$

• 模运算（Modulo）：
  结果 $r$ 的符号与除数 $b$ 相同。
  例：$7 \mod 3 = 1$（因 $7 = 3 \times 2 + 1$）；$(-7) \mod 3 = 2$（因 $-7 = 3 \times (-3) + 2$，商 $q$ 向负无穷取整）。

• 取余（Remainder）：
  结果 $r$ 的符号与被除数 $a$ 相同。
  例：$(-7) \mod 3$ 若为取余，则结果为 $-1$（因 $-7 = 3 \times (-2) + (-1)$，商 $q$ 向零取整）。

2. C++中的%运算符

C++的%本质是取余运算，结果符号与被除数一致：

• 正数运算：与模运算结果相同（如 7 % 3 = 1，3 % 7 = 3）。
• 负数运算：结果符号与被除数一致（如 -7 % 3 = -1，7 % (-3) = 1）。

若需在C++中实现模运算（结果与除数同号），需手动调整：
$\text{mod}(a, b) = (a \% b + b) \% b$

3. 模运算的核心性质

设 $a, b, c, m$ 为整数，$m > 0$，则：

1. $(a + b) \mod m = [(a \mod m) + (b \mod m)] \mod m$（加法分配律）
2. $(a \times b) \mod m = [(a \mod m) \times (b \mod m)] \mod m$（乘法分配律）
3. $(a - b) \mod m = [(a \mod m) - (b \mod m) + m] \mod m$（减法需补(m)防负）
4. 若 $a \equiv b \mod m$，则 $a + c \equiv b + c \mod m$（同余可加减）

二、实战案例

实战案例

案例1：模运算与取余的区别及调整

问题：对比C++取余与数学模运算的结果，实现通用模运算函数。

c++

#include <iostream>
using namespace std;

// 实现数学意义上的模运算（结果与除数同号）
int mod(int a, int b) {
    int r = a % b;
    // 若结果与除数异号，加b调整
    if ((r > 0 && b < 0) || (r < 0 && b > 0)) {
        r += b;
    }
    return r;
}

int main() {
    cout << "C++取余: -7 % 3 = " << -7 % 3 << endl;       // -1（与被除数同号）
    cout << "数学模运算: mod(-7, 3) = " << mod(-7, 3) << endl; // 2（与除数同号）
    
    cout << "C++取余: 7 % -3 = " << 7 % -3 << endl;       // 1（与被除数同号）
    cout << "数学模运算: mod(7, -3) = " << mod(7, -3) << endl; // -2（与除数同号）
    return 0;
}

关键点：通过判断取余结果与除数的符号是否一致，不一致则加除数调整，得到数学意义上的模运算结果。

案例2：利用模运算简化大数计算

问题：计算 $(a \times b + c) \mod m$，其中 $a, b, c$ 可能为大数（如 $10^9$），避免直接计算溢出。

c++

#include <iostream>
using namespace std;

// 计算 (a*b + c) mod m，避免中间结果溢出
long long bigMod(long long a, long long b, long long c, long long m) {
    // 分步取模：先算a*b mod m，再加c mod m，最后整体mod m
    long long part1 = (a % m) * (b % m) % m; // 乘法取模
    long long part2 = c % m;                 // 加法项取模
    return (part1 + part2) % m;              // 总和取模
}

int main() {
    long long a = 1e9, b = 1e9, c = 1e9, m = 1e5;
    cout << bigMod(a, b, c, m) << endl; // 结果为 (1e18 + 1e9) mod 1e5 = 90000 + 90000 mod 1e5 = 80000
    return 0;
}

原理：利用模运算的乘法和加法分配律，分步对中间结果取模，避免 $(a \times b)$ 直接计算导致的溢出（$(1e9 \times 1e9 = 1e18)$ 超过 int 范围，但 long long 可容纳，此处仅为演示分步取模的必要性）。

案例3：模运算在周期性问题中的应用

问题：已知今天是星期一，求 $n$ 天后是星期几（1~7分别代表周一到周日）。

c++

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    // 今天是周一（1），n天后的星期数：(1 + n - 1) mod 7 + 1 = (n mod 7) + 1
    // 解释：先转为0-6范围（周一为0），加n后取模，再转回1-7
    int day = (n % 7) + 1;
    // 处理n为负数的情况（过去的天数）
    if (day < 1) day += 7;
    cout << day << endl;
    return 0;
}

关键点：星期是周期为7的循环，用模运算将 $n$ 映射到0-6范围，再调整为1-7的星期数，同时兼容负数（过去的天数）。

三、信奥赛应用场景

信奥赛应用场景

1. 大数简化计算：
   当计算结果仅需模 $m$ 的值时（如“求 $(10^{100} \mod 7)$”），利用模运算性质分步计算，避免直接处理大数（见案例2）。

2. 同余问题：
   如“判断一个数是否为3的倍数”（数字和模3为0）、“寻找满足 $a \equiv b \mod m$ 的最小正整数 $a$”等。

3. 加密与哈希：
   凯撒密码（字母移位加密）：(c - 'A' + k) % 26 + 'A'（将字母 $c$ 后移 $k$ 位，模26确保在字母范围内）。

4. 循环结构：
   循环队列（用 (front + 1) % size 计算下一个位置）、环形数组访问等。

5. 数论算法基础：
   最大公约数（gcd）、扩展欧几里得算法、素数判定（米勒-拉宾测试）等均依赖模运算。

四、避坑指南

避坑指南

1. 负数处理错误：

   • 陷阱：直接使用 a % m 处理负数时，结果可能为负（如 -5 % 3 = -2），导致后续逻辑错误（如数组索引越界）。
   • 解决：用 (a % m + m) % m 统一转为非负结果（适用于 $m > 0$）。

2. 模0错误：

   • 陷阱：除数为0时，a % 0 会导致程序运行时错误（除以零）。
   • 解决：提前判断除数是否为0，如 if (m == 0) { /* 报错或特殊处理 */ }。

3. 溢出风险：

   • 陷阱：计算 (a % m) * (b % m) 时，若 $m$ 接近 $1e9$，则乘积可能超过 int 范围（如 $(1e9 \mod 1e9) * (1e9 \mod 1e9) = 0$，但更大的 $m$ 可能导致溢出）。
   • 解决：用 long long 存储中间结果，如 ( (long long)(a % m) * (b % m) ) % m。

4. 模运算与除法混淆：

   • 陷阱：误认为 (a / b) % m = (a % m) / (b % m)（不成立，如 (6 / 2) % 3 = 0，但 (6%3)/(2%3) = 0/2 = 0 看似成立，实际不通用）。
   • 解决：模运算对除法不满足分配律，需用乘法逆元（仅当 $b$ 与 $m$ 互质时存在）。

重要

• 核心价值：模运算通过将大数映射到有限范围，简化计算并避免溢出，是处理周期性问题、加密、数论算法的基础工具。
• C++实现要点：明确%是取余运算，需手动调整以获得数学模运算结果；利用加法、乘法分配律分步取模，确保计算安全。
• 竞赛提示：普及组中模运算多结合周期性问题（如星期、日期）、大数简化（如求和/积模$m$）出现，需重点掌握负数处理和溢出防范，避免因符号或范围错误丢分。

整数唯一分解定理

一、概念解析

整数唯一分解定理

整数唯一分解定理（又称算术基本定理）是初等数论的核心定理之一，为整数的质因数分解提供了理论基础，其核心内容如下：

整数唯一分解定理

1. 定理定义

任何大于1的自然数 $n$，都可以唯一地分解为有限个质数的乘积，即：
$n = p_1^{e_1} \times p_2^{e_2} \times \dots \times p_k^{e_k}$
其中：

• $p_1, p_2, \dots, p_k$ 是互不相同的质数（素数）；
• $e_1, e_2, \dots, e_k$ 是正整数（表示对应质数的指数）；
• 唯一性：若不考虑质数的排列顺序，这种分解方式是唯一的。

2. 关键术语

• 质因数：分解式中的质数 $p_i$（如12的质因数为2和3）；
• 指数：表示质因数在分解式中出现的次数（如12 = 2²×3¹，指数分别为2和1）；
• 平凡分解：质数的分解式为其本身（如5 = 5¹）。

3. 定理意义

唯一分解定理将复杂的整数分解为最基本的质数“积木”，使得整数的性质（如因数个数、最大公约数、最小公倍数）可通过质因数的指数运算推导，是数论问题求解的“万能钥匙”。

二、实战案例

实战案例

案例1：质因数分解（试除法实现）

问题：输入大于1的整数 $n$，输出其唯一分解式（如 $n=12$ 输出 2^2 * 3^1）。

c++

#include <iostream>
#include <vector>
using namespace std;

// 存储质因数及其指数（pair: 质数, 指数）
vector<pair<long long, int>> factorize(long long n) {
    vector<pair<long long, int>> factors;
    
    // 分解2（唯一偶质数，单独处理优化效率）
    if (n % 2 == 0) {
        int cnt = 0;
        while (n % 2 == 0) {
            cnt++;
            n /= 2;
        }
        factors.emplace_back(2, cnt);
    }
    
    // 分解奇数（从3开始，步长为2）
    for (long long i = 3; i * i <= n; i += 2) {
        if (n % i == 0) {
            int cnt = 0;
            while (n % i == 0) {
                cnt++;
                n /= i;
            }
            factors.emplace_back(i, cnt);
        }
    }
    
    // 若剩余n > 1，说明是未分解的质数
    if (n > 1) {
        factors.emplace_back(n, 1);
    }
    
    return factors;
}

int main() {
    long long n;
    cin >> n;
    auto factors = factorize(n);
    
    // 输出分解式
    for (int i = 0; i < factors.size(); ++i) {
        cout << factors[i].first << "^" << factors[i].second;
        if (i != factors.size() - 1) {
            cout << " * ";
        }
    }
    return 0;
}

关键点：

• 优先分解2（唯一偶质数），再从3开始枚举奇数，减少循环次数；
• 枚举到 $\sqrt{n}$ 即可，剩余 $n > 1$ 必为质数；
• 用 long long 避免大整数溢出（如 $n \leq 10^{12}$）。

案例2：利用分解式求因数个数

问题：输入 $n$，根据唯一分解定理求其正因数的个数（如 $n=12=2^2×3^1$，因数个数为 $(2+1)×(1+1)=6$）。

c++

#include <iostream>
#include <vector>
using namespace std;

vector<pair<long long, int>> factorize(long long n) {
    // 同案例1的分解函数
    vector<pair<long long, int>> factors;
    if (n % 2 == 0) {
        int cnt = 0;
        while (n % 2 == 0) { cnt++; n /= 2; }
        factors.emplace_back(2, cnt);
    }
    for (long long i = 3; i * i <= n; i += 2) {
        if (n % i == 0) {
            int cnt = 0;
            while (n % i == 0) { cnt++; n /= i; }
            factors.emplace_back(i, cnt);
        }
    }
    if (n > 1) factors.emplace_back(n, 1);
    return factors;
}

// 因数个数 = (e1+1) * (e2+1) * ... * (ek+1)
int countFactors(long long n) {
    if (n == 1) return 1; // 1的因数只有自身
    auto factors = factorize(n);
    int res = 1;
    for (auto &p : factors) {
        res *= (p.second + 1);
    }
    return res;
}

int main() {
    long long n;
    cin >> n;
    cout << countFactors(n) << endl;
    return 0;
}

原理：每个质因数 $p_i$ 可选择的指数为 $0, 1, ..., e_i$（共 $e_i+1$ 种），因数总数为所有选择的乘积。

案例3：求最大公约数（gcd）与最小公倍数（lcm）

问题：输入两个数 $a, b$，利用质因数分解求 $\gcd(a,b)$ 和 $\text{lcm}(a,b)$。

c++

#include <iostream>
#include <unordered_map>
using namespace std;

// 分解并存储质因数到哈希表（质数 -> 指数）
unordered_map<long long, int> factorMap(long long n) {
    unordered_map<long long, int> mp;
    if (n == 1) return mp;
    if (n % 2 == 0) {
        int cnt = 0;
        while (n % 2 == 0) { cnt++; n /= 2; }
        mp[2] = cnt;
    }
    for (long long i = 3; i * i <= n; i += 2) {
        if (n % i == 0) {
            int cnt = 0;
            while (n % i == 0) { cnt++; n /= i; }
            mp[i] = cnt;
        }
    }
    if (n > 1) mp[n] = 1;
    return mp;
}

long long gcdByFactor(long long a, long long b) {
    auto mpA = factorMap(a), mpB = factorMap(b);
    long long gcd = 1;
    for (auto &[p, e] : mpA) {
        if (mpB.count(p)) { // 取共同质因数的最小指数
            int minE = min(e, mpB[p]);
            for (int i = 0; i < minE; ++i) {
                gcd *= p;
            }
        }
    }
    return gcd;
}

long long lcmByFactor(long long a, long long b) {
    auto mpA = factorMap(a), mpB = factorMap(b);
    long long lcm = 1;
    // 合并两个哈希表，取每个质因数的最大指数
    for (auto &[p, e] : mpA) {
        int maxE = e;
        if (mpB.count(p)) maxE = max(e, mpB[p]);
        for (int i = 0; i < maxE; ++i) {
            lcm *= p;
        }
    }
    for (auto &[p, e] : mpB) {
        if (!mpA.count(p)) { // 处理mpB独有的质因数
            for (int i = 0; i < e; ++i) {
                lcm *= p;
            }
        }
    }
    return lcm;
}

int main() {
    long long a, b;
    cin >> a >> b;
    cout << "gcd: " << gcdByFactor(a, b) << endl;
    cout << "lcm: " << lcmByFactor(a, b) << endl;
    return 0;
}

原理：

• $\gcd(a,b)$ 是所有共同质因数取最小指数的乘积；
• $\text{lcm}(a,b)$ 是所有质因数（包括独有的）取最大指数的乘积；
• 公式：$\text{lcm}(a,b) = a \times b / \gcd(a,b)$（实际计算中更常用，但此处展示分解法原理）。

三、信奥赛应用场景

信奥赛应用场景

1. 因数相关问题：

   • 求因数个数（如案例2）、因数和（公式：$\prod (1 + p_i + p_i^2 + ... + p_i^{e_i})$）；
   • 求第k小的因数（分解后按指数组合枚举）。

2. 最大公约数与最小公倍数：
   除案例3的分解法外，辗转相除法更高效，但分解法适用于需要质因数的场景（如“求多个数的lcm”）。

3. 数的性质判断：

   • 判断完全平方数（所有质因数的指数均为偶数）；
   • 判断质数（分解后只有一个质因数且指数为1）；
   • 判断互质数（gcd为1，即无共同质因数）。

4. 模运算与加密：
   如RSA加密中，大质数分解的困难性是安全性的基础；求乘法逆元需基于质因数判断互质性。

四、避坑指南

避坑指南

1. 分解不彻底：

   • 陷阱：试除法循环终止条件错误（如用 i <= n 而非 i * i <= n），导致遗漏质因数（如分解28时，若循环到4就停止，会遗漏7）。
   • 解决：严格用 i * i <= n 循环，最后判断剩余 n > 1 并加入质因数。

2. 数据溢出：

   • 陷阱：分解大数（如 $10^{12}$）时，$i * i$ 可能超过 long long 范围（如 $i=1e9$ 时，$i*i=1e18$ 已达 long long 上限，更大的i会溢出）。
   • 解决：循环条件改为 $i <= n / i$（等价于 $i*i <= n$，但避免溢出）。

3. 特殊值处理遗漏：

   • 陷阱：未处理 n=1（无质因数，因数个数为1），或 n=0（不满足定理条件，需提前排除）。
   • 解决：函数入口先判断 n <= 1，返回空或特殊值（如案例2中 countFactors(1) = 1）。

4. 效率低下：

   • 陷阱：对大质数（如 $1e9+7$）直接试除到 $\sqrt{n}$，耗时过长（约 $3e4$ 次循环，虽能通过普及组数据，但可优化）。
   • 解决：结合质数筛法（如埃氏筛预处理小质数），优先用小质数试除。

重要

• 核心地位：整数唯一分解定理是数论的“基石”，将整数的各种性质转化为质因数的指数运算，为因数、gcd、lcm等问题提供统一解法。
• 编程要点：质因数分解的试除法是基础实现，需优化循环范围（到 $\sqrt{n}$）、处理偶质数、用 long long 防溢出；基于分解结果可快速推导因数个数、gcd等。
• 竞赛提示：普及组中，唯一分解定理多与因数计算、数的性质判断结合，需重点掌握分解的高效实现和特殊值处理，避免因分解不彻底或溢出导致结果错误。

辗转相除法（欧几里得算法）

一、概念解析

辗转相除法

辗转相除法（又称欧几里得算法）是求两个整数最大公约数（gcd）的高效算法，其核心思想基于数论中的整除性质，是信奥赛中处理最大公约数问题的核心工具。

概念解析

1. 基本定义

• 最大公约数（gcd）：两个整数 $a$ 和 $b$ 的最大公约数是能同时整除 $a$ 和 $b$ 的最大正整数，记为 $\gcd(a, b)$。
  例：$\gcd(12, 18) = 6$，因6是能同时整除12和18的最大整数。

• 辗转相除法原理：
  对于任意两个正整数 $a$ 和 $b$（$a \geq b$），有：
  $\gcd(a, b) = \gcd(b, a \mod b)$
  其中 $a \mod b$ 表示 $a$ 除以 $b$ 的余数（$0 \leq a \mod b < b$）。
  递归终止条件：当 $b = 0$ 时，$\gcd(a, 0) = a$。

2. 算法步骤

以计算 $\gcd(48, 18)$ 为例：

1. $48 \mod 18 = 12$ → 转为求 $\gcd(18, 12)$；
2. $18 \mod 12 = 6$ → 转为求 $\gcd(12, 6)$；
3. $12 \mod 6 = 0$ → 终止，返回6。

二、实战案例

实战案例

案例1：递归实现辗转相除法

问题：用递归方式实现辗转相除法，计算两个整数的最大公约数。

c++

#include <iostream>
using namespace std;

// 递归实现gcd：gcd(a,b) = gcd(b, a%b)
long long gcdRecursive(long long a, long long b) {
    if (b == 0) return a; // 终止条件：gcd(a,0) = a
    return gcdRecursive(b, a % b);
}

int main() {
    long long a, b;
    cin >> a >> b;
    // 确保输入为非负数（若有负数，取绝对值）
    a = abs(a);
    b = abs(b);
    cout << gcdRecursive(a, b) << endl;
    return 0;
}

关键点：递归调用中，每次将问题规模缩小（用余数替代原数），直到余数为0，返回当前的被除数。

案例2：迭代实现辗转相除法（更高效）

问题：用迭代方式实现辗转相除法，避免递归栈开销，适合大整数计算。

c++

#include <iostream>
using namespace std;

// 迭代实现gcd
long long gcdIterative(long long a, long long b) {
    a = abs(a); // 处理负数
    b = abs(b);
    while (b != 0) {
        long long temp = b; // 暂存b
        b = a % b; // 用余数更新b
        a = temp;  // 用原b更新a
    }
    return a;
}

int main() {
    long long a, b;
    cin >> a >> b;
    cout << gcdIterative(a, b) << endl;
    return 0;
}

关键点：通过循环迭代，用余数不断替换原数，直到余数为0，此时的 $a$ 即为最大公约数，效率高于递归（无函数调用开销）。

案例3：求最小公倍数（lcm）

问题：利用 $\text{lcm}(a, b) = \frac{|a \times b|}{\gcd(a, b)}$ 计算最小公倍数。

c++

#include <iostream>
using namespace std;

long long gcd(long long a, long long b) {
    a = abs(a);
    b = abs(b);
    while (b != 0) {
        long long temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// 最小公倍数 = 两数乘积的绝对值 / 最大公约数
long long lcm(long long a, long long b) {
    if (a == 0 || b == 0) return 0; // 0和任何数的lcm是0
    return (abs(a) / gcd(a, b)) * abs(b); // 先除后乘，避免溢出
}

int main() {
    long long a, b;
    cin >> a >> b;
    cout << lcm(a, b) << endl;
    return 0;
}

关键点：计算 $(a \times b) 可能溢出（如 (a) 和 (b) 接近 (10^9) 时），因此先计算 $|a| / \gcd$，再乘以 $|b|)，减少溢出风险。

案例4：求多个数的最大公约数

问题：输入 $n$ 个整数，求它们的最大公约数（如 $(\gcd(12, 18, 24) = 6)$）。

c++

#include <iostream>
#include <vector>
using namespace std;

long long gcd(long long a, long long b) {
    a = abs(a);
    b = abs(b);
    while (b != 0) {
        long long temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// 多个数的gcd：逐步求当前gcd与下一个数的gcd
long long gcdMultiple(const vector<long long>& nums) {
    if (nums.empty()) return 0; // 空集合返回0
    long long currentGcd = nums[0];
    for (size_t i = 1; i < nums.size(); ++i) {
        currentGcd = gcd(currentGcd, nums[i]);
        if (currentGcd == 1) break; // gcd为1时，无需继续计算
    }
    return currentGcd;
}

int main() {
    int n;
    cin >> n;
    vector<long long> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }
    cout << gcdMultiple(nums) << endl;
    return 0;
}

原理：多个数的最大公约数等于前两个数的gcd与第三个数的gcd，以此类推（满足结合律）。若中途gcd为1，可提前终止（1与任何数的gcd都是1）。

三、信奥赛应用场景

信奥赛应用场景

1. 直接求gcd/lcm：
   如“求两个数的最大公约数”“求三个数的最小公倍数”等基础题（普及组常考）。

2. 分数化简：
   将分数 $\frac{a}{b}$ 化简为最简形式，分子分母同除以 $\gcd(a, b)$（如 $\frac{12}{18} = \frac{12/6}{18/6} = \frac{2}{3}$）。

3. 同余方程与模运算：
   求解线性同余方程 $ax \equiv b \mod m$ 时，需先判断 $\gcd(a, m)$ 是否整除 $b$（有解的充要条件）。

4. 互质性判断：
   若 $\gcd(a, b) = 1$，则 $a$ 和 $b$ 互质（如判断两个数是否互质，用于加密或概率问题）。

5. 排列组合问题：
   计算组合数 $C(n, k)$ 时，通过gcd化简分子分母的乘积，避免大数溢出。

四、避坑指南

避坑指南

1. 负数处理错误：

   • 陷阱：直接对负数使用辗转相除法（如 $\gcd(-12, 18)$），因C++中 % 结果与被除数同号，可能导致迭代异常。
   • 解决：先对输入取绝对值（如案例1、2中 a = abs(a)），确保参与运算的是正数。

2. 零值处理错误：

   • 陷阱：输入包含0时（如 $\gcd(0, 0)$ 无意义，$\gcd(a, 0) = |a|$），未特殊处理导致逻辑错误。
   • 解决：明确规则：$\gcd(0, 0) = 0$（约定），$\gcd(a, 0) = |a|$，在代码中优先处理0的情况。

3. 溢出风险：

   • 陷阱：计算lcm时直接用 abs(a * b) / gcd，当 $a$ 和 $b$ 接近 $10^9$ 时，$a \times b$ 会超过 long long 范围（如 $1e9 \times 1e9 = 1e18$，接近 long long 上限 $9e18$，更大的数会溢出）。
   • 解决：改为 $(|a| / \gcd) * |b|$（先除后乘），因 $\gcd$ 能整除 $a$，除法结果为整数，避免中间乘积过大。

4. 效率误解：

   • 陷阱：认为递归实现与迭代实现效率相同，或对极小数（如 $a=1$）过度优化。
   • 解决：迭代实现效率更高（无递归栈开销），适合大整数；无需对小数特殊处理，辗转相除法本身对小数计算极快。

重要

• 核心价值：辗转相除法是求最大公约数的最优算法，时间复杂度为 $O(\log \min(a, b))$，远快于枚举法，是处理数论问题的基础工具。
• 实现要点：优先用迭代实现（高效），处理负数（取绝对值）和零值（明确规则），计算lcm时注意先除后乘防溢出。
• 竞赛提示：普及组中，辗转相除法常与lcm、分数化简、互质性判断结合，需熟练掌握其原理和边界处理，避免因负数、零值或溢出导致错误。

素数筛法：埃氏筛法与线性筛法

一、概念解析

素数筛法：埃氏筛法与线性筛法

素数筛法是高效批量快速筛选出一定范围内所有素数的算法，在信奥赛中常用于预处理素数，为后续数论问题（如质因数分解、素数判断）提供支持。

素数筛法：埃氏筛法与线性筛法

1. 埃氏筛法（Eratosthenes Sieve）

• 基本思想：从2开始，将每个素数的倍数标记为合数，未被标记的数即为素数。
• 原理：若一个数 $n$ 未被小于它的素数标记，则 $n$ 必为素数（因为它没有小于自身的因数）。
• 时间复杂度：$O(n \log \log n)$，接近线性，适合 $n \leq 10^7$ 的场景。

2. 线性筛法（欧拉筛）

• 基本思想：在埃氏筛基础上优化，每个合数仅被其最小质因数标记一次，确保时间复杂度达到线性。
• 核心优化：对于每个数 $i$，用已找到的素数 $p$ 标记 $i \times p$，当 $p$ 是 $i$ 的因数时停止（避免重复标记）。
• 时间复杂度：$O(n)$，适合 $n \leq 10^8$ 的大规模筛选。

二、实战案例

实战案例

案例1：埃氏筛法实现

问题：筛选出1~n中的所有素数，并统计素数个数（如 $n=30$ 时，素数有2,3,5,7,11,13,17,19,23,29，共10个）。

c++

#include <iostream>
#include <vector>
using namespace std;

// 埃氏筛法：返回1~n中的素数列表
vector<int> sieveEratosthenes(int n) {
    if (n < 2) return {}; // 小于2的数没有素数
    vector<bool> isPrime(n + 1, true); // 标记是否为素数
    isPrime[0] = isPrime[1] = false;   // 0和1不是素数
    
    for (int i = 2; i * i <= n; ++i) { // 只需循环到sqrt(n)
        if (isPrime[i]) { // 若i是素数，标记其倍数为合数
            // 从i*i开始标记（小于i*i的倍数已被更小的素数标记）
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    
    // 收集所有素数
    vector<int> primes;
    for (int i = 2; i <= n; ++i) {
        if (isPrime[i]) {
            primes.push_back(i);
        }
    }
    return primes;
}

int main() {
    int n;
    cin >> n;
    vector<int> primes = sieveEratosthenes(n);
    
    cout << "素数个数：" << primes.size() << endl;
    for (int p : primes) {
        cout << p << " ";
    }
    return 0;
}

关键点：

• 从 $i \times i$ 开始标记倍数（优化点，因更小的倍数已被之前的素数标记）；
• 外层循环到 $\sqrt{n}$ 即可（更大的数若未被标记，必为素数）。

案例2：线性筛法实现

问题：用线性筛法筛选1~n中的素数，确保每个合数仅被标记一次。

c++

#include <iostream>
#include <vector>
using namespace std;

// 线性筛法：返回1~n中的素数列表
vector<int> sieveEuler(int n) {
    if (n < 2) return {};
    vector<bool> isPrime(n + 1, true);
    vector<int> primes; // 存储已找到的素数
    
    for (int i = 2; i <= n; ++i) {
        if (isPrime[i]) { // 若i是素数，加入列表
            primes.push_back(i);
        }
        // 用已找到的素数标记i的倍数
        for (int p : primes) {
            if (i * p > n) break; // 超出范围，停止
            isPrime[i * p] = false; // 标记合数
            if (i % p == 0) break; // p是i的最小质因数，避免重复标记
        }
    }
    
    return primes;
}

int main() {
    int n;
    cin >> n;
    vector<int> primes = sieveEuler(n);
    
    cout << "素数个数：" << primes.size() << endl;
    for (int p : primes) {
        cout << p << " ";
    }
    return 0;
}

核心优化解析：

• 当 $i \% p == 0$ 时，$p$ 是 $i$ 的最小质因数，因此 $p$ 也是 $i \times p$ 的最小质因数，继续循环会导致用更大的素数标记，违反“最小质因数唯一标记”原则，故需 break。

案例3：筛法应用——预处理素数判断

问题：预处理1~n的素数表，快速判断任意数是否为素数（如多次查询时优化效率）。

c++

#include <iostream>
#include <vector>
using namespace std;

// 预处理素数标记表
vector<bool> preprocessPrimes(int n) {
    if (n < 2) return vector<bool>(0);
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false;
    
    for (int i = 2; i * i <= n; ++i) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    return isPrime;
}

int main() {
    int n, q;
    cin >> n >> q; // n: 范围，q: 查询次数
    vector<bool> isPrime = preprocessPrimes(n);
    
    while (q--) {
        int x;
        cin >> x;
        if (x < 2 || x > n) cout << "不是素数" << endl;
        else cout << (isPrime[x] ? "是素数" : "不是素数") << endl;
    }
    return 0;
}

优势：预处理时间 $O(n \log \log n)$，单次查询时间 $O(1)$，适合多次查询的场景（如q=1e5次）。

三、信奥赛应用场景

信奥赛应用场景

1. 素数统计与判断：
   如“统计1~n中素数的个数”“判断m个数字是否为素数”，筛法预处理可大幅提升效率。

2. 质因数分解加速：
   预处理最小质因数（线性筛可同时记录每个数的最小质因数），分解时通过最小质因数快速拆分（如 $n = p \times m$，递归分解m）。

3. 数论函数计算：
   如计算欧拉函数 $\phi(n)$（小于n且与n互质的数的个数），线性筛可在筛选过程中同步计算。

4. 密码学相关问题：
   如生成大素数用于RSA加密模拟（普及组中多为小规模场景）。

5. 区间素数问题：
   如“找出[a, b]范围内的素数”，可先用筛法处理 $[2, \sqrt{b}]$ 内的素数，再标记区间内的合数（分段筛思想）。

四、避坑指南

避坑指南

1. 内存溢出：

   • 陷阱：对大n（如 $n=1e8$）使用 vector<bool> 存储标记表，虽 vector<bool> 是位压缩存储（1字节存8个标记），但1e8仍需约12MB，若用普通数组（bool[]）则需100MB以上，可能超内存限制。
   • 解决：根据题目内存限制选择筛法（埃氏筛适合n≤1e7，线性筛可到1e8）；必要时用分段筛处理更大范围。

2. 循环范围错误：

   • 陷阱：埃氏筛外层循环写成 i <= n 而非 i * i <= n，导致效率低下（对n=1e7，循环次数从3e3增至1e7）。
   • 解决：严格遵循 i * i <= n 的外层循环条件，利用“更大的数若未被标记则为素数”的性质。

3. 线性筛的break条件遗漏：

   • 陷阱：实现线性筛时忘记 if (i % p == 0) break，导致合数被多次标记（如6会被2和3分别标记），时间复杂度退化为 $O(n \log n)$。
   • 解决：牢记“每个合数仅被最小质因数标记”的原则，必须添加break条件。

4. 初始化错误：

   • 陷阱：未将 isPrime 数组初始化为 true，或误将0和1标记为素数，导致结果错误。
   • 解决：初始化时统一设为 true，再手动标记0和1为 false。

5. 数据类型溢出：

   • 陷阱：计算 i * p 时，若i和p较大（如i=1e9，p=1e9），乘积超过 int 范围导致溢出，标记错误位置。
   • 解决：用 long long 存储中间结果，如 if ((long long)i * p > n) break。

重要

• 两种筛法对比：
  埃氏筛实现简单，适合中小规模（n≤1e7）；线性筛通过“最小质因数唯一标记”实现线性时间，适合大规模（n≤1e8），但代码稍复杂。
• 核心应用：筛法是预处理素数的“利器”，为素数判断、质因数分解、数论函数计算等提供高效支持，是信奥赛数论模块的基础。
• 竞赛提示：普及组中，埃氏筛因实现简单更常考，需熟练掌握其优化细节（从i*i开始标记）；线性筛在处理大n时优势明显，需理解其“最小质因数”优化原理。实际应用中，需根据n的范围和内存限制选择合适筛法，避免内存溢出和效率问题。