约数专题

求因数

单个数求因数： 枚举到 $\sqrt n$ ， $O(\sqrt n)$

多个数求因数： 枚举倍数， $O(n\log n)$

最大公约数

时间复杂度： $O(\log{(a+b)} )$

代码：

递归版：略

非递归版：

int gcd(int a,int b){
	int t;
	while(b){
		t=a%b;
		a=b;
		b=t;
	}
	return a;
}

算术基本定理

描述：对任意 $n \in \mathbb N_+ (n \ge 2)$ ， $n$ 都可以被唯一表示为 $ \prod_{i=1}^kp_i^{\alpha_i} (k \in \mathbb N_+,p_i \text{为质数} )$ 的形式，

推论：

1. $n$ 的正因数个数为 $\prod_{i=1}^k(\alpha_i+1)$ ，
2. $n$ 的正因数之和为 $\prod_{i=1}^k \sum_{j=0}^{\alpha_i} p^j$ 。

例题

1. 反质数

题面：（P1463）

2. Hankson的趣味题

题面：（P1072）

3. X-factor Chains（因数链）

题面：（HFOJ A1628）给定 $x \in \mathbb N_+ (x\le 10^5)$ ，求 $x$ 的大于 $1$ 的因子组成的满足前一项能整除后一项的序列的最大长度，以及满足最大长度的序列个数。

4. 聪明的燕姿

题面：（P4397）给定 $S \in \mathbb N_+ (S \le 2 \times 10^9)$ ，求出所有的 $n$ 使得 $n$ 的正因数之和为 $S$。