标签：数论

数据结构与算法刷题之【数论】篇

<p>汇总数论相关的数据结构与算法刷题笔记，讲解数值的整数次方、快速幂、质因数分解等知识点，涵盖剑指offer与蓝桥杯题型并给出Java实现与复杂度分析。</p>

AcWing 蓝桥杯AB组辅导课 08、数论

<p>本文是 AcWing 蓝桥杯 AB 组辅导课第八讲「数论」的学习笔记，涵盖等差数列的最大公约数、X 的因子与算术基本定理、聪明的燕姿、五指山与扩展欧几里得、最大比例、C 循环、正则问题、糖果状压 DP 等题解。</p>

AcWing 蓝桥杯AB组辅导课 10、疑难杂题

<p>本文是 AcWing 蓝桥杯 AB 组辅导课第十讲「疑难杂题」的学习笔记，涵盖修改数组的单链表式并查集、倍数问题背包加贪心、斐波那契快速幂与龟速乘、距离的 tarjan 离线 LCA，以及剪格子、组合数问题、模拟散列表等题解。</p>

快速幂及矩阵快速幂分析及代码实现

<p>讲解快速幂及矩阵快速幂的原理与代码实现，通过将指数不断二分把时间复杂度从O(N)降低到O(logN)，并结合斐波那契前n项和等例题给出Java实现与取模处理细节。</p>

欧几里得与扩展欧几里得算法(含推导过程及代码)

<p>讲解欧几里得算法（辗转相除法）与扩展欧几里得算法的原理、裴蜀定理及推导过程，说明如何求解ax+by=gcd(a,b)的整数解，并给出完整的Java代码实现与应用场景，为求解线性同余方程等数论问题打下基础。</p>

算数基本定理

<p>讲解算数基本定理的内容，说明任何大于1的自然数都能唯一分解为若干质因子的乘积，并结合X的因子链等例题给出质因数分解的应用方式与解题思路。</p>

约数个数及约数之和

<p>讲解约数个数与约数之和的公式及其证明过程，通过质因数分解推导(a1+1)(a2+1)…与等比求和公式，并结合聪明的燕姿等例题给出实际应用与解题思路，帮助读者掌握数论题目的推导方法。</p>

辗转相除以及辗转相减法

<p>讲解辗转相除法（欧几里得算法）与辗转相减法（更相减损法）的原理与适用场景，说明二者在求最大公约数时的联系与区别，并给出完整的Java代码实现与复杂度分析。</p>