整除理论作为初等数论的重要组成部分,是研究时间最早的数学领域,其历史可追溯到公元前六世纪,发源于古希腊并在公元前四世纪以前形成完善的体系.这个问题大约在毕达哥拉斯时代(公元前六世纪)已经出现,并且可能发展出了辗转相除法(首次出现于欧几里得《几何原本》).这是一个有效算法,时间复杂度为$\mathtt{O}(n^2\log{n})$.
欧几里得给出过这个算法的证明.事实上,数论的研究在那时已经有了现代数学的雏形,其本质上不同于古中国的经验主义数学,是逻辑推演的结果.
这个算法本质上基于这么一个公式:$(a,b)=(b,a\bmod b)~~(a\ge b)$.
这个挺简单的公式,要证明起来需要从唯一分解定理开始讲,事实上还是不那么简单的.有个非常简单的证明思路,就是令$p=(a,b)$,$c=a/p,d=b/p,e=(a\bmod b)/p$,那么显然有$c\equiv e\pmod{d}$,此时可判定$(c,d)=1$,否则可以在两边的结果处都除以一个$(c,d)$,也就是结果要乘上$(c,d)$,显然与最大公约数的定义不符.
int gcd(a,b)= [a if b==0 else gcd(b,a%b)]
inline long gcd(long a,long b){
return b?gcd(b,a%b):a;
}
更相相损术出处:《九章算术》.
可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。
主要思想:将两数迭代相减,如果两数都为偶数则将两数都取其半,答案乘2.直到此算法中两数相等为止.
//Obsoleted exptime method.
#include "algorithm"
inline int gcd_substraction(int a,int b){
if(a<b) std::swap(a,b);
a-=b;
if(a & 1 || b & 1) return gcd_substraction(a,b); else return gcd(a>>1,b>>1)<<1;
}
这个算法可以是对更相相损术的另一种理解.
Stein论文地址
主要思想: 在上面算法的基础上,每当其中有一个数有2因子就除去.
//better O(n^2) method
inline long long gcd_binary(long long a,long long b){
if(!b) return a;
if(!a) return b;
int qa=0,qb=0;
while(!(a&1)) a>>=1,++qa;
while(!(b&1)) b>>=1,++qb;
if(qb<qa) qa=qb;
if(a<b) std::swap(a,b);
return gcd_binary(a-b,b)<<qa;
}
注意:此方法只在大整数上更快.
测试代码