快速幂是一种高效计算幂次的算法，它可以将计算 $a^n$ 的时间复杂度从朴素算法的 $O(n)$ 降低到 $O(log n)$。下面为你详细介绍快速幂算法的原理和实现，以及如何在 C++ 中实现它。

原理

快速幂算法的核心思想是利用幂次的二进制分解。假设我们要计算 $a^n$，可以将 $n$ 表示为二进制形式，例如：$n = 2^k_1+2^k_2+\cdots+2^k_m$。那么 $a^n$ 就可以写成 $a^{2^k_1}\times a^{2^k_2}\times\cdots\times a^{2^k_m}$。

例如，计算 $a^{13}$，因为 $13$ 的二进制表示是 $1101$，即 $13 = 2^3 + 2^2 + 2^0$，所以 $a^{13}=a^{2^3}\times a^{2^2}\times a^{2^0}$。

代码实现

以下是使用 C++ 实现快速幂的代码：

#include <iostream>

// 快速幂函数
long long fastPower(long long a, long long n) {
    long long result = 1;
    while (n > 0) {
        if (n & 1) {  // 判断 n 的二进制最后一位是否为 1
            result *= a;
        }
        a *= a;  // a 平方
        n >>= 1;  // n 右移一位，相当于除以 2
    }
    return result;
}

int main() {
    long long a = 2;
    long long n = 13;
    long long ans = fastPower(a, n);
    std::cout << a << " 的 " << n << " 次幂是: " << ans << std::endl;
    return 0;
}

代码解释

1. 初始化结果：result 初始化为 1，用于存储最终结果。
2. 循环条件：当 n > 0 时，继续循环。
3. 判断二进制最后一位：使用 n & 1 判断 n 的二进制最后一位是否为 1，如果是 1，则将当前的 a 乘到 result 中。
4. 平方操作：将 a 平方，即 a *= a。
5. 右移操作：将 n 右移一位，相当于将 n 除以 2。
6. 返回结果：当 n 变为 0 时，循环结束，返回 result。

复杂度分析

• 时间复杂度：$O(log n)$，因为每次循环 n 都会减半。
• 空间复杂度：$O(1)$，只使用了常数级的额外空间。

取模运算

在实际应用中，幂次的结果可能会非常大，为了避免溢出，通常会对结果取模。以下是带有取模运算的快速幂代码：

#include <iostream>

const long long MOD = 1e9 + 7;

// 带取模的快速幂函数
long long fastPowerMod(long long a, long long n) {
    long long result = 1;
    a %= MOD;  // 防止 a 过大
    while (n > 0) {
        if (n & 1) {
            result = (result * a) % MOD;
        }
        a = (a * a) % MOD;
        n >>= 1;
    }
    return result;
}

int main() {
    long long a = 2;
    long long n = 13;
    long long ans = fastPowerMod(a, n);
    std::cout << a << " 的 " << n << " 次幂对 " << MOD << " 取模的结果是: " << ans << std::endl;
    return 0;
}

这个代码在每次乘法操作后都对结果取模，确保结果不会溢出。

通过枚举法求最小公倍数

#include<iostream>
using namespace std;
int main() {
	int a,b;
	scanf("%d %d",&a,&b);//a < b
	if(a > b){
		swap(a,b);
	}
	for(int i=1;;i++){
		if(i*a % b == 0){
			printf("%d",i*a);
			break;
		}
	}
	
	return 0;
}

C++ 初等数论教程 —— 0基础详细讲解

📘 前言：什么是初等数论？

初等数论（Elementary Number Theory）是研究整数的基本性质的数学分支。它不涉及复杂的数学工具如实分析或复分析，而是主要研究整数的除法、最大公约数、最小公倍数、素数、模运算等内容。

在编程中，尤其是算法设计、密码学、竞赛编程等领域，初等数论是非常重要的基础知识。

---

🧮 第一章：基本概念与符号

1.1 整数与自然数

• 整数集合：... -3, -2, -1, 0, 1, 2, 3 ...
• 自然数集合：0 或者 1 开始（不同定义），通常我们用 unsigned int 表示自然数范围的正整数。

1.2 取模运算（Modulo）

取模运算是一个非常关键的操作。

• 记作：a % b，表示 a 除以 b 的余数。
• 规则：
  • 如果 a < 0，则结果也为负（C++ 中行为需注意）。
  • 例如：7 % 5 = 2；(-7) % 5 = -2（不是最简形式的模运算结果）。

#include <iostream>
using namespace std;

int main() {
    cout << "7 % 5 = " << 7 % 5 << endl;     // 输出 2
    cout << "-7 % 5 = " << -7 % 5 << endl;   // 输出 -2
}

✅ 注意：在 C++ 中，模运算的结果符号和第一个操作数相同。

---

🔢 第二章：整除性与最大公约数

2.1 整除（Divisibility）

如果整数 a 能被整数 b 整除，记作：b | a，即存在整数 k，使得 a = b × k。

例如：3 | 6，因为 6 = 3 × 2；但 3 ∤ 7。

判断方式：

if (a % b == 0) {
    cout << b << " 整除 " << a << endl;
}

---

2.2 最大公约数 GCD（Greatest Common Divisor）

两个整数的最大公约数是指能同时整除这两个数的最大正整数。

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

这是求最大公约数的经典方法，基于以下定理：

gcd(a, b) = gcd(b, a % b)

递归实现：

int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

测试代码：

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

int main() {
    int a = 48, b = 18;
    cout << "gcd(" << a << ", " << b << ") = " << gcd(a, b) << endl;
    return 0;
}

输出：

gcd(48, 18) = 6

---

📐 第三章：最小公倍数 LCM（Least Common Multiple）

最小公倍数是两个整数能同时被整除的最小正整数。

公式：

lcm(a, b) = a * b / gcd(a, b)

⚠️ 注意：为了避免溢出，建议使用 long long 类型。

long long lcm(int a, int b) {
    return (long long)a * b / gcd(a, b);  // 需要先定义前面的 gcd 函数
}

---

🧩 第四章：素数（质数）

4.1 定义

素数（Prime Number）是指大于1且只能被1和自身整除的整数。

例如：2, 3, 5, 7, 11...

4.2 素数判断函数

我们可以写一个简单函数来判断一个数是否为素数。

bool isPrime(int n) {
    if (n <= 1) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    
    for (int i = 3; i*i <= n; i += 2) {
        if (n % i == 0)
            return false;
    }
    return true;
}

测试：

cout << "Is 17 prime? " << isPrime(17) << endl;  // 输出 1（true）
cout << "Is 20 prime? " << isPrime(20) << endl;  // 输出 0（false）

---

4.3 枚举小于等于 n 的所有素数（埃拉托色尼筛法 Sieve of Eratosthenes）

这是一个经典的生成所有素数的方法。

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

void sieve(int n) {
    vector<bool> is_prime(n+1, true);
    is_prime[0] = is_prime[1] = false;

    for (int i = 2; i*i <= n; ++i) {
        if (is_prime[i]) {
            for (int j = i*i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }

    cout << "小于等于 " << n << " 的素数有：\n";
    for (int i = 2; i <= n; ++i) {
        if (is_prime[i])
            cout << i << " ";
    }
    cout << endl;
}

调用：

sieve(30);

输出：

小于等于 30 的素数有：
2 3 5 7 11 13 17 19 23 29

---

🧮 第五章：同余与模运算进阶

5.1 同余关系（Congruence）

如果两个整数 a 和 b 在除以 m 后余数相同，那么称它们对 m 同余，记作：

a ≡ b (mod m)

等价于：m | (a - b)

例如：10 ≡ 3 (mod 7)，因为 10 - 3 = 7，能被 7 整除。

---

5.2 模运算的性质

• (a + b) % m = ((a % m) + (b % m)) % m
• (a - b) % m = ((a % m) - (b % m) + m) % m
• (a × b) % m = ((a % m) × (b % m)) % m

这些性质在处理大数时非常重要。

---

5.3 快速幂（Exponentiation Modulo）

快速计算 $a^b \mod m$。

long long mod_pow(long long a, long long b, long long m) {
    long long result = 1;
    a %= m;
    while (b > 0) {
        if (b % 2 == 1)
            result = (result * a) % m;
        a = (a * a) % m;
        b /= 2;
    }
    return result;
}

测试：

cout << "3^5 mod 7 = " << mod_pow(3, 5, 7) << endl;  // 结果是 5

---

📋 总结：常用的数论函数一览表

功能	函数名	时间复杂度
判断素数	isPrime(n)	O(√n)
最大公约数	gcd(a, b)	O(log min(a,b))
最小公倍数	lcm(a, b)
筛法求素数	sieve(n)	O(n log log n)
快速幂模运算	mod_pow(a,b,m)	O(log b)

---

💡 编程练习建议

1. 编写程序输入一个数 n，输出其所有因数。
2. 输入两个整数，输出它们的最大公约数和最小公倍数。
3. 编写程序判断并输出某个范围内所有的素数。
4. 实现一个加密/解密小程序，用模幂来做简单的 RSA 加密模拟。
5. 写一个函数判断一个数是不是回文素数（既是回文数又是素数）。

---

📚 下一步推荐学习内容

✅ 扩展欧几里得算法（用于求 ax + by = gcd(a,b) 的解）
✅ 同余方程与逆元（Modular Inverse）
✅ 中国剩余定理（CRT）
✅ 数论函数（如 φ(n) 欧拉函数）
✅ BSGS 算法（大步小步算法）解决离散对数问题

---

📌 提示：学习过程中可以结合 LeetCode、洛谷、Codeforces 平台上的题目进行练习，比如：

• LeetCode 204. 计数质数
• LeetCode 365. 水壶问题（贝祖定理）
• Codeforces 上的数论分类题库

---

如果你希望继续深入某一部分（如扩展欧几里得、欧拉函数、模线性方程等），欢迎继续提问！

初等数论是数学的一个分支，专注于整数的性质及其相互关系。对于完全没有基础的学习者来说，可以从以下几个基本概念和主题开始学习：

1. 基础概念

• 整数：理解什么是整数（正整数、负整数和零）。
• 除法与余数：了解如何进行整数除法以及什么是余数。引入模运算的概念，即 a mod b 表示 a 除以 b 的余数。

2. 质数与合数

• 质数：只能被 1 和自身整除的大于1的自然数。
• 合数：除了 1 和它本身之外还能被其他数整除的自然数。
• 质因数分解：每个合数都可以写成几个质数的乘积的形式，这种表示方法称为质因数分解。

3. 最大公约数 (GCD) 与最小公倍数 (LCM)

• 最大公约数 (GCD)：两个或多个整数共有约数中最大的一个。
• 最小公倍数 (LCM)：两个或多个整数共有的倍数中最小的一个。GCD 和 LCM 之间存在一定的关系，即两个数的乘积等于它们的最大公约数和最小公倍数的乘积。

4. 模运算

• 同余：如果两个数 a 和 b 除以 m 的余数相同，则称 a 和 b 关于模 m 同余，记作 a ≡ b (mod m)。

5. 进一步探索

• 欧拉定理与费马小定理：这些定理涉及到了同余的一些重要性质。
• 线性同余方程：形式为 ax ≡ b (mod m) 的方程。
• 中国剩余定理：解决一系列线性同余方程的方法。

基础准备

• 了解C++语言基础，包括变量、数据类型、控制结构（如if - else、循环）、函数等。

初等数论知识与C++实现

1. 整除与余数
   • 学习整除的概念，即一个整数能够被另一个整数整除的关系。
   • 在C++中，可以使用取模运算符%来计算余数。例如，a % b表示a除以b的余数。当a % b == 0时，说明a能被b整除。
   • 示例代码：

#include <iostream>

int main() {
    int a = 10, b = 3;
    if (a % b == 0) {
        std::cout << a << " 能被 " << b << " 整除。" << std::endl;
    } else {
        std::cout << a << " 除以 " << b << " 的余数是 " << a % b << std::endl;
    }
    return 0;
}

2. 最大公因数与最小公倍数
   • 介绍辗转相除法求最大公因数的原理：两个整数的最大公因数等于其中较小的数和两数相除余数的最大公因数。
   • 用C++实现辗转相除法：

#include <iostream>

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

int main() {
    int num1 = 24, num2 = 36;
    int gcdResult = gcd(num1, num2);
    std::cout << "最大公因数是: " << gcdResult << std::endl;
    // 最小公倍数 = 两数之积 / 最大公因数
    int lcmResult = (num1 * num2) / gcdResult;
    std::cout << "最小公倍数是: " << lcmResult << std::endl;
    return 0;
}

3. 质数与合数
   • 定义质数为大于1且除了1和自身外不能被其他正整数整除的数，合数是除了质数以外的数。
   • 编写C++函数判断一个数是否为质数：

#include <iostream>
#include <cmath>

bool isPrime(int num) {
    if (num < 2) {
        return false;
    }
    for (int i = 2; i <= std::sqrt(num); i++) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}

int main() {
    int number = 17;
    if (isPrime(number)) {
        std::cout << number << " 是质数。" << std::endl;
    } else {
        std::cout << number << " 是合数。" << std::endl;
    }
    return 0;
}

4. 素数筛法
   • 讲解埃拉托斯特尼筛法，用于找出一定范围内的所有质数。其原理是从2开始，将每个质数的倍数都标记为合数，剩下的就是质数。
   • 用C++实现埃拉托斯特尼筛法：

#include <iostream>
#include <vector>

void sieveOfEratosthenes(int n) {
    std::vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false;

    for (int p = 2; p * p <= n; p++) {
        if (isPrime[p]) {
            for (int i = p * p; i <= n; i += p) {
                isPrime[i] = false;
            }
        }
    }

    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            std::cout << i << " ";
        }
    }
}

int main() {
    int n = 30;
    std::cout << "小于等于 " << n << " 的质数有: ";
    sieveOfEratosthenes(n);
    return 0;
}

5. 同余
   • 介绍同余的概念：如果两个整数a和b除以同一个正整数m所得的余数相同，则称a和b对于模m同余，记作a ≡ b (mod m)。
   • 实现判断两个数是否同余的C++函数：

#include <iostream>

bool isCongruent(int a, int b, int m) {
    return (a % m == b % m);
}

int main() {
    int num1 = 17, num2 = 29, mod = 6;
    if (isCongruent(num1, num2, mod)) {
        std::cout << num1 << " 和 " << num2 << " 对于模 " << mod << " 同余。" << std::endl;
    } else {
        std::cout << num1 << " 和 " << num2 << " 对于模 " << mod << " 不同余。" << std::endl;
    }
    return 0;
}

练习与实践

• 完成一些基础的数论相关的编程练习题，如判断一个数是否为完全数、求一个数的所有因数等。
• 尝试解决一些简单的实际问题，例如在密码学中，利用初等数论的知识进行简单的加密和解密操作。

进阶学习

• 学习更深入的数论算法，如中国剩余定理、费马小定理等，并使用C++实现。
• 了解数论在计算机科学中的更多应用，如哈希函数、随机数生成等。

在学习过程中，要多思考、多实践，遇到问题及时查阅资料或向他人请教。同时，可以参考一些专业的数论书籍，如《初等数论》（第三版，潘承洞、潘承彪著），加深对初等数论知识的理解。

C++ 编程语言本身并不直接提供数论的教程，但是我们可以讨论如何使用 C++ 来实现初等数论中的一些基本概念和算法。对于 0 基础的学习者来说，首先需要了解一些基础的编程概念，如变量、循环、条件语句等，之后可以开始学习如何用 C++ 实现数论中的概念。

以下是一个简单的路径来学习 C++ 中的初等数论：

1. 学习 C++ 基础

• 数据类型：了解整型(int)、浮点型(float, double)等基本数据类型。
• 控制结构：包括 if-else 条件判断、for 循环、while 循环等。
• 函数：学习如何定义和调用函数。
• 数组与向量：掌握数组的基本操作以及标准模板库(STL)中的 vector 类。

2. 初等数论基础

在具备了基础的 C++ 知识后，可以开始学习数论的基础知识，比如：

• 质数：理解什么是质数，如何检测一个数是否为质数。
• 最大公约数(GCD)：学习欧几里得算法来计算两个数的最大公约数。
• 最小公倍数(LCM)：利用 GCD 计算 LCM。
• 模运算：了解取模运算的概念及其应用。

3. 使用 C++ 实现数论算法

• 质数检测：编写函数来判断一个给定的数字是否是质数。
• GCD 和 LCM：使用 C++ 实现欧几里得算法来找到两个数的最大公约数，并进一步计算它们的最小公倍数。
• 素因数分解：编写程序将一个整数分解为其素因数的乘积。

4. 进一步探索

随着你对 C++ 和初等数论的理解加深，你可以尝试更复杂的算法和问题，如：

• 大数运算
• 模幂运算
• 数论变换