前言

欧几里德算法作为有着非常简短的实现的算法,可能很多初学者(包括当时的我)都不求甚解。本文给出了GCD、LCM的性质,以及欧几里德算法的实现、证明和时间复杂度推导。

什么是欧几里得算法

最大公约数问题是最早被研究的算法问题之一了,并且是ACM竞赛中能涉及到的很多数论内容,比如模线性方程,模线性方程组的基础。

欧几里得算法 (Euclidean algorithm) ,即大部分选手所知的“辗转相除法”,其核心在于不断将两数规模变小,最后实现对数时间内求解两个数的最大公约数。

其核心是:\[gcd(a,b) = gcd(b, a \% b)\]

名词解释

  1. 最大公约数:即最大公因子,能够同时整除a和b的最大因子,记作gcd(a, b),或gcd
  2. 最小公倍数:能够被a和b整除的最小数,记作lcm(a, b),或lcm。
  3. %:指的是取余运算(取模运算),用例: a % b
  4. |:指的是整除运算,a | b表明a可以整除b,即a是b的因子

GCD和LCM的一些性质

  1. a, b都能分解为有限个素数的积
  2. gcd(a, b)中只含a,b的全部公共素因子
  3. lcm(a, b)中含有a,b的所有素因子
  4. \(gcd\%lcm=0\)
  5. \(gcd
Read the rest

为什么用快速幂

对于求解\({a^b}\)的问题,我们能想到的朴素算法:

int ans = 1;
for (int i = 0; i < b; i++)
    ans *= a;

而快速幂可以在O(logn)时间内解出。

什么是快速幂

先举一个例子,我们计算\({5^8}\)只需要3步,即分别求得\({5^2}\)、\({5^4}\)、\({5^8}\)。
因为每次相乘,幂次都增长一倍,我们只需要logn次就可以让幂逼近n。

所以,我们可以将b通过二进制分解为形如10011的数,则\({\rm{b}} = {2^{k1}} + {2^{k2}} + {2^{k3}} \ldots \)。
因为\({a^{{2^{k1}}}}\)到\({a^{{2^{kmax}}}}\)可以通过\({a^{{2^1}}}\)、\({a^{{2^2}}}\)\({a^{{2^3}}}\)这样在递推kmax次中得到,所以\({a^b} = {a^{{2^{k1}}}} * {a^{{2^{k2}}}}\)可以在O(lo… Read the rest