约数

若整数n除以整数d的余数为0，即d能整除n，则称d是n的约数，n是d的倍数，记为 [math]\displaystyle{ d|n }[/math] 。

算数基本定理的推论

在算数基本定理中，若正整数N被唯一分解为[math]\displaystyle{ N = \prod_{i=1}^m p_i^{c_i} }[/math]，其中 [math]\displaystyle{ c_i }[/math] 都是正整数，[math]\displaystyle{ p_i }[/math] 都是素数，且满足 [math]\displaystyle{ p_1\lt p_2\lt \cdots \lt p_m }[/math] ，则N的正约数集合可写作：[math]\displaystyle{ \{{p_1}^{b_1},{p_2}^{b_2},\cdots,{p_m}^{b_m}\} }[/math] , 其中 [math]\displaystyle{ 0 \leq b_i \leq c_i }[/math]

N的正约数个数为 [math]\displaystyle{ \prod_{i=1}^m {c_i+1} }[/math]

N的所有正约数的和为[math]\displaystyle{ \prod_{i=1}^m {\sum_{j=0}^{c_i} {{p_i}^j}} }[/math]

实现

求N的正约数集合，若 [math]\displaystyle{ d \geq \sqrt N }[/math] 是N的约数，则 [math]\displaystyle{ \frac{N}{d} \leq \sqrt N }[/math] 也是N的约数。

因此，只需要扫描 [math]\displaystyle{ d=1 \backsim \sqrt N }[/math] 尝试d能否整除N，若能整除，则 [math]\displaystyle{ \frac{N}{d} }[/math] 也是N的约数。时间复杂度为[math]\displaystyle{ O(\sqrt N) }[/math] 。

int f[MAX_N];
int m;
void divisor_factor(int n) {
	for (int i = 0; i*i <= n; ++i) {
		if (n % i == 0) {
			f[++m] = i;
			if (i != n/i)
				f[++m] = n/i;
		}
	}
}

参考资料

1. 算法竞赛进阶指南，李煜东，139页