约数与倍数

定义

若 $a|b$ （"|"为整除符号）即 $b \equiv 0(\bmod\ a)$ ，则称 $a$ 是 $b$ 的约数，也称因数，而 $b$ 是 $a$ 的倍数。

性质（整数惟一分解定理的推论）

任何正整数都是其本身的约数，也是其本身的倍数。
$1$ 是任何正整数的约数，任何正整数都是 $1$ 的倍数。

唯一质因数分解定律：若整数 $N≥2$ ，那么 $N=p_1^{r_1} p_2^{r_2}\dots p_k^{r_k}$ （ $p_i$ 为素数， $r_i\geq 0$ ），由此可得：

$N$ 的正约数集合为： $\{x|x=p_1^{b_1} p_2^{b_2} \dots p_k^{b_k}\}$ （ $0\leq b_i\leq r_i，b_i\in N^*$ ）
$N$ 的正约数个数为：
$(r_1+1)\times (r_2+1)\times \dots \times(r_k+1)=\prod\limits_{i=1}^k (r_i+1)$ 。
除了完全平方数，约数总是成对出现的，即 $d\leq \sqrt n$ 和 ${N\over d} \leq \sqrt n$ 都是 $N$ 的约数。
$N$ 的约数个数上界为 $2\sqrt N$ 。
$N$ 的所有正约数的和为：
$(1+p_1+p_1^2+\dots+p_1^{r_1})\times\dots\times(1+p_k+p_k^2+\dots+p_k^{r_k})=\prod\limits_{i=1}^k (\sum\limits_{j=0}^{r_i} (p_i)^j)$

最大公约数

定义

设 $a$ 和 $b$ 是不都为 $0$ 的整数， $c$ 为满足 $c|a$ 且 $c|b$ 的最大整数，则称 $c$ 是 $a$ 和 $b$ 的最大公约数，记为 $gcd(a,b)$ 或 $(a,b)$ 。

性质

最大公约数具有以下性质；

$gcd(a,b)=gcd(b,a)=gcd⁡(−a,b)=gcd(|a|,|b|)$
$1\leq gcd(a,b)\leq \min(a,b)$
若 $d|a$ 且 $d|b$ ，则 $d|gcd(a,b)$ （"|"是整除符号）
$gcd(a,0)=a$
$gcd⁡(a,ka)=a (k\in Z)$

求解算法

方法一：直接暴力枚举，过程如下：

从 $\min⁡(a,b)$ 到 $1$ 枚举 $x$ ，并判断 $x$ 是否能同时整除 $a$ 和 $b$ ，如果可以则输出 $x$ 退出循环。

时间复杂度为 $O(\min⁡(a,b))$ 。

方法二：分解素因数，过程如下：

$a=p_1^{r_1}p_2^{r_2}\dots p_k^{r_k} ，b=p_1^{s_1}p_2^{s_2}\dots p_k^{s_k}$ ， $r_i,s_i \geq 0$ 且不会同时为 $0 (1\leq i\leq n)$ ，则 $gcd(a,b)=p_1^{\min(r1，s1)}p_2^{\min(r2，s2)}\dots p_k^{\min(rk，sk)}$ 。

代码如下：

int Decompose(int a, int b) {
	int ans = 1;
	for(int x = 2; x * x <= min(a,b); x++){
		while(a % x == 0 && b % x == 0) a /= x, b /= x, ans *= x;
		while(a % x == 0) a /= x;
		while(b % x == 0) b /= x;
	} 
	if (a % b == 0) ans *= b;
	else if (b % a == 0) ans *= a;
	return ans;
}

方法三：欧几里得算法：

“两个整数 $a,b(a\geq b)$ 的公约数集合与 $a−b$ 和 $b$ 的公约数集合相同”，可得： $gcd⁡(a,b)=gcd⁡(b,a \bmod b)$ ，俗名曰“辗转相减法”。

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

如果输入一组数 1 1000000000，可以设想该算法的执行效率，因为每一次都会直接将 $b$ 减少 $1$ ，所以会减 $10^9$ 次才能使其为 $0$ ，效率甚至不如暴力枚举，那么，我们可以用模运算来代替减，就是小学奥数中常说的“辗转相除法”！代码如下：

int gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b, a % b);
    // 或者可以写三目运算符成如下形式
    // return (b == 0) ? a : gcd(b, a % b);
}

时间复杂度分析：

根据 $gcd(a,b)=gcd(b,a \bmod b)$ ，设 $a>b$ ：

当 $a\geq 2b$ 时， $b\leq a/2$ ， $b$ 的规模至少缩小一半；

当 $a<2b$ 时， $a \bmod b<a/2$ ，余数的规模至少缩小一半；

所以时间复杂度为 $O(\log a+b)$ ，在实际使用中，复杂度远远达不到如此。

方法四：库函数

当然，我相信没有人会像写这个东西，所以 c++ 提供了库函数 __gcd()，其用法与上面的 gcd 函数一样，传入两个参数 $a$ 和 $b$ 即可返回 $a$ 与 $b$ 的最大公约数，要注意的是，这个函数属于 algorithm 库，而不是 cmath，用之前记得要写头文件。

比如 int res=__gcd(12,18)，那么 $res$ 的数值就被更改为了 $6$ 。

最坏时间复杂度也为 $O(\log a+b)$ ，所以很少有人闲的没事干写 gcd 函数，直接 __gcd(a,b) 就行了。

最小公倍数

定义

$a$ 和 $b$ 最小的正公倍数为 $a$ 和 $b$ 的最小公倍数，记作 $lcm(a,b)$ 。

性质

最小公倍数有如下性质：

$lcm(a,b)=ab/gcd(a,b)$
若 $a|m$ 且 $b|m$ ，则 $lcm(a,b)|m$
若 $m,a,b$ 是正整数，则 $lcm(ma,mb)=m∗lcm(a,b)$ 。

求解算法

求两个数的最小公倍数：

利用性质： $lcm(a,b)=ab/gcd(a,b)$ ，可写出代码：

int lcm(int a,int b) {
    long long res=a*b;
    res/=__gcd(a,b);
    return res;
}

求多个数的最小公倍数：

依照求两个数最小公倍数的方法类推，可以先求 $a_1,a_2$ 的最小公倍数 $b_1$ ，再求 $b_1$ 与 $a_3$ 的最小公倍数 $b_2$ ，再求 $b_2$ 与 $a_4$ 的最小公倍数 $b_3$ $\dots\dots$

代码如下：

long long lcm(int a[],int n) {
	long long ans=1;
	for(int i=1;i<=n;++i)
		ans=ans*a[i]/__gcd(ans,1ll*a[i]);
	return ans;
}

练习题

P1463 [POI2001] [HAOI2007] 反素数
 P1072 [NOIP2009 提高组] Hankson 的趣味题
 [BZOJ 1876] Super GCD

约数与倍数