无编辑摘要 |
(→实现) |
||
(未显示同一用户的5个中间版本) | |||
第2行: | 第2行: | ||
== 算数基本定理的推论 == | == 算数基本定理的推论 == | ||
在[[算数基本定理]]中,若正整数N被唯一分解为<math>N = \prod_{i=1}^m p_i^{c_i}</math>,其中 <math>c_i</math> 都是正整数,<math>p_i</math> 都是素数,且满足 <math>p_1<p_2<\cdots <p_m</math> ,则N的正约数集合可写作:<math>\{{p_1}^{b_1},{p_2}^{b_2},\cdots,{p_m}^{b_m}\}</math> , 其中 <math>0 \leq b_i \leq c_i</math> | |||
N的正约数个数为 <math>\prod_{i=1}^m {c_i+1}</math> | N的正约数个数为 <math>\prod_{i=1}^m {c_i+1}</math> | ||
N的所有正约数的和为<math>\prod_{i=1}^m {\sum_{j=0}^{c_i} {{p_i}^j}}</math> | N的所有正约数的和为<math>\prod_{i=1}^m {\sum_{j=0}^{c_i} {{p_i}^j}}</math> | ||
== 实现 == | |||
求N的正约数集合,若 <math>d \geq \sqrt N</math> 是N的约数,则 <math>\frac{N}{d} \leq \sqrt N</math> 也是N的约数。 | |||
因此,只需要扫描 <math>d=1 \backsim \sqrt N</math> 尝试d能否整除N,若能整除,则 <math>\frac{N}{d}</math> 也是N的约数。时间复杂度为<math>O(\sqrt N)</math> 。 | |||
<syntaxhighlight lang="c" line> | |||
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; | |||
} | |||
} | |||
} | |||
</syntaxhighlight> | |||
== 参考资料 == | |||
# 算法竞赛进阶指南,李煜东,139页 | |||
[[Category:数学]] |
2022年2月24日 (四) 15:45的最新版本
若整数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;
}
}
}
参考资料
- 算法竞赛进阶指南,李煜东,139页